×

# Corollary to Euler's Theorem

When we studied Euler's Theorem back in college (in Switzerland), the professor mentioned the following simple corollary, leaving the proof as an exercise: $a^{\phi(n)+k}\equiv{a^k}\pmod{n}$ for all positive integers $$a$$ and $$n$$, as long as $$k$$ is $$\geq$$ the multiplicity of all the primes in the factorization of $$n$$. Can you prove (or disprove) this?

For example, if $$n=2^3\times{5}\times{7^4}$$ , we want $$k\geq{4}$$

Thus we can say that "in modular arithmetic, all exponential functions eventually become periodic."

Note by Otto Bretscher
2 years, 4 months ago

Sort by:

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=2^3\times{5}\times{7^4}$$ , it suffices to prove the congruency modulo $$2^3, 5$$ and $$7^4$$.

So, let $$p^m$$ be a prime power factor of $$n$$. If $$p\not|{a}$$, then we have $$a^{\phi(p^m)}\equiv{1}\pmod{p^m}$$ by Euler's Theorem. Since $$\phi(p^m)|\phi(n)$$ , we have $$a^{\phi(n)}\equiv{1}\pmod{p^m}$$ as well and therefore $$a^{\phi(n)+k}\equiv{a^k}\pmod{p^m}$$ as claimed.

If $$p|a$$, then $$p^m|a^k$$ since $$k\geq{m}$$ , so that $$a^{\phi(n)+k}\equiv{0}\equiv{a^k}\pmod{p^m}.$$ · 2 years, 4 months ago

Can't we use euler's theorem and multiply a^k to both sides giving result. · 2 years, 4 months ago

Euler's theorem is valid iff $$\gcd(a,n)=1$$ where $$a,n\in\Bbb{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. · 2 years, 4 months ago

Ya here we have to deal extra case of gcd not being 1 rest seems using euler theorem and some arithmetic . · 2 years, 4 months ago

Ohk , thanx! · 2 years, 4 months ago

Forgot it .Now it seems slight difficult thanx. · 2 years, 4 months ago

Yes i also thought the same..... · 2 years, 4 months ago

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. · 1 year, 3 months ago

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.) · 1 year, 11 months ago

@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. · 2 years, 4 months ago

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 ;) · 2 years, 4 months ago