My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By idontknow
  • 1 Post By Martin Hopf
  • 1 Post By skipjack
Reply
 
LinkBack Thread Tools Display Modes
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$.

$$ $$
Martin Hopf is offline  
 
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.
idontknow is offline  
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?
Thanks from idontknow

Last edited by Martin Hopf; July 14th, 2019 at 01:12 AM.
Martin Hopf is offline  
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
skipjack is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
a⋅a−1, divisibility, divisible, find, integer, na−n, number theory, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to find if a number is divisible by n YuvalM Elementary Math 2 October 27th, 2015 06:28 AM
The difference between an integer and the sum of its digits is always divisible by 9 simco50 Number Theory 5 October 5th, 2014 10:24 AM
polynomial divisible by integer gelatine1 Algebra 4 January 7th, 2013 09:39 PM
Least integer having all digits 4 divisible by 169 proglote Number Theory 5 May 25th, 2011 05:38 PM





Copyright © 2019 My Math Forum. All rights reserved.