My Math Forum Find all a such that n^aâˆ’n is divisible by aâ‹…(aâˆ’1) for any integer n.
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 July 10th, 2019, 07: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, 08:55 AM #2 Senior Member   Joined: Dec 2015 From: somewhere Posts: 549 Thanks: 83 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 09:00 AM.
July 14th, 2019, 12: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 01:12 AM.

 July 14th, 2019, 03:10 AM #4 Global Moderator   Joined: Dec 2006 Posts: 20,823 Thanks: 2160 $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 Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post YuvalM Elementary Math 2 October 27th, 2015 06:28 AM simco50 Number Theory 5 October 5th, 2014 10:24 AM gelatine1 Algebra 4 January 7th, 2013 09:39 PM proglote Number Theory 5 May 25th, 2011 05:38 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top