×

# 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, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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, 10 months ago

Can't we use euler's theorem and multiply a^k to both sides giving result.

- 2 years, 10 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, 10 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, 10 months ago

Ohk , thanx!

- 2 years, 10 months ago

Forgot it .Now it seems slight difficult thanx.

- 2 years, 10 months ago

Yes i also thought the same.....

- 2 years, 10 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, 9 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.)

- 2 years, 5 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, 10 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, 10 months ago