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."

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ 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

Sort by:

TopNewestLet 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}.$

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\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.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Yes i also thought the same.....

Log in to reply

@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 ;)

Log in to reply

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.)

Log in to reply

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.

Log in to reply