 My Math Forum Find all a such that n^a−n is divisible by a⋅(a−1) for any integer n.

 Number Theory Number Theory Math Forum

 July 10th, 2019, 08:47 AM #1 Member   Joined: Oct 2013 Posts: 60 Thanks: 6 Find all a such that n^a−n is divisible by a⋅(a−1) for any integer n.  $$a \cdot (a-1) \ \mid \ n^{a}-n \ \ \ \forall \ n \in \mathbb{Z}$$ Find all $a$. July 12th, 2019, 09:55 AM #2 Senior Member   Joined: Dec 2015 From: Earth Posts: 832 Thanks: 113 Math Focus: Elementary Math Supposing the expression on the right is a polynomial (degree 2) then $\displaystyle a=2 \;$ , $\displaystyle 2(2-1) \; | \; n^{2}-n =n(n-1)$. Since $\displaystyle n(n-1)$ is the product of two adjacent numbers, they are divisible by 2. Maybe applying (p divides n^p-n for p-prime) will solve the problem. Thanks from Martin Hopf Last edited by idontknow; July 12th, 2019 at 10:00 AM. July 14th, 2019, 01:54 AM   #3
Member

Joined: Oct 2013

Posts: 60
Thanks: 6

Yes, $$a=2$$ is a solution. You gave a nice proof.

Quote:
 Maybe applying (p divides n^p-n for p-prime) will solve the problem.
This is true for all primes. Unfortunately it will not serve as a primality test as the Carmichael numbers also pass this test.

Nevertheless I think $$a$$ has to be prime.

$$a \cdot (a-1) \ \mid \ n^{a}-n \ = \ a \cdot (a-1) \ \mid \ n \cdot (n^{a-1}-1) \ \ \ \forall \ n \in \mathbb{Z} \ .$$

Conjecture: has only solutions if $$\phi (a)= a-1$$ with $$\phi ()$$ denotes Euler's totient function.
This implies $$a$$ to be prime. By substitution of $$\phi (a)= a-1$$ we get:
$$a \cdot \phi (a) \ \mid \ n \cdot (n^{\phi (a)}-1) \ \ \ \forall \ n \in \mathbb{Z} \ \ , \ a \in \mathbb{P} \ .$$

Let $$a=3$$:

$$6 \ \mid \ n^{3}-n \ = \ 6 \ \mid \ n\cdot(n^{2}-1) \ = \ 6 \ \mid \ n \cdot(n-1)\cdot (n+1) \ \ \ \forall \ n \in \mathbb{Z} \ .$$
So we have 3 adjacent factors on the right side: $$(n-1)\cdot n \cdot (n+1)$$.
One of them is divisible by 3, and one or two of them is/are even.
Thus the right side is divisible by $$2\cdot3=6 \ \ \ \forall \ n \in \mathbb{Z} \$$.

$$a=3$$ is a solution!

What further solutions can we find?

Last edited by Martin Hopf; July 14th, 2019 at 02:12 AM. July 14th, 2019, 04:10 AM #4 Global Moderator   Joined: Dec 2006 Posts: 21,114 Thanks: 2329 $a = 7$ is a solution and $a = 43$ may be a solution. Beyond that, I've no idea. Thanks from idontknow Tags a⋅a−1, divisibility, divisible, find, integer, na−n, number theory, proof Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post YuvalM Elementary Math 2 October 27th, 2015 07:28 AM simco50 Number Theory 5 October 5th, 2014 11:24 AM gelatine1 Algebra 4 January 7th, 2013 10:39 PM proglote Number Theory 5 May 25th, 2011 06:38 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      