When we studied Euler's Theorem back in college (in Switzerland), the professor mentioned the following simple corollary, leaving the proof as an exercise: for all positive integers and , as long as is the multiplicity of all the primes in the factorization of . Can you prove (or disprove) this?
For example, if , we want
Thus we can say that "in modular arithmetic, all exponential functions eventually become periodic."
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Let me try to outline a proof.
It suffices to prove the congruency modulo all the prime power factors of n. For example, if n=23×5×74 , it suffices to prove the congruency modulo 23,5 and 74.
So, let pm be a prime power factor of n. If p∣a, then we have aϕ(pm)≡1(modpm) by Euler's Theorem. Since ϕ(pm)∣ϕ(n) , we have aϕ(n)≡1(modpm) as well and therefore aϕ(n)+k≡ak(modpm) as claimed.
If p∣a, then pm∣ak since k≥m , so that aϕ(n)+k≡0≡ak(modpm).
Log in to reply
Can't we use euler's theorem and multiply a^k to both sides giving result.
Log in to reply
Euler's theorem is valid iff gcd(a,n)=1 where a,n∈Z+. The result in this note, however, doesn't have the restriction that gcd(a,n)=1 and hence you cannot directly use Euler's Theorem here.
Log in to reply
Yes i also thought the same.....
@Tijmen Veltman proved this for k=1 and square-free n in this note.
He might be interested in proving/disproving this one too, so I'm tagging him here.
Log in to reply
Interesting! Thank you for letting me know.
The result I quote is sometimes mentioned in introductory Number Theory texts, usually as an exercise. I have never found any use for it... until I joined Brilliant ;)
Let the GCD of a and n be g. Then, a=gc and n=gd.
The rest of the proof is left to the reader as an exercise. (Just kidding, I got to go now and I will finish it later.)
I made a problem about this a while back (although I just now read this note): Divisibility of power differences. It was when I was writing the wiki on Carmichael numbers.
Proof for the corollary:
let n=p1a1p2a2...pmambe the standard factorisation of n.
k is greater than the multiplicity of all the primes in the factorization of n is equivalent to k≥max{a1,a2,...,am}.
if a,pi are co-prime, aϕ(n)+k=aϕ(p1a1)ϕ(p2a2)...ϕ(pmam)+k≡ak(modpiai).
if a,pi are not co-prime, vpi(ak)=kvpi(a)≥ai⇒ak≡0(modpiai), where vp(n) denotes the exponent of p in the prime factorization of n. ϕ(n)+k>k⇒aϕ(n)+k≡0(modpiai). Hence aϕ(n)+k≡ak≡0(modpiai).
Hence, for all positive a,n, aϕ(n)+k≡ak(modpiai).
Since this is true for all i∈{1,2,...,m}, the result follows.