# Thread: Euler Totient Function Question

1. ## Euler Totient Function Question

Hello,
I just need to know if this holds :

$\displaystyle a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

$\displaystyle a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

Thank you all

2. Originally Posted by Bacterius
Hello,
I just need to know if this holds :

$\displaystyle a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

$\displaystyle a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

Thank you all
Did you check whether $\displaystyle \text{gcd}(b, \varphi(n))=1$?

3. Originally Posted by Bacterius
Hello,
I just need to know if this holds :

$\displaystyle a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

$\displaystyle a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}$ For any $\displaystyle a$ coprime with $\displaystyle n$.

This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

Thank you all
$\displaystyle b^c \bmod{\varphi(\varphi(n))} = b^c+d\varphi(\varphi(n))$ for some $\displaystyle d$

$\displaystyle a^{b^c+d\varphi(\varphi(n))}=a^{b^c}a^{d\varphi(\v arphi(n))}\equiv a^{b^c} \bmod{n}$

Since $\displaystyle (a,n)=1\implies (a^{b^c},n)=1$ so the cancelation property holds and we get $\displaystyle a^{d\varphi(\varphi(n))}\equiv1\bmod{n}$ which isn't always true.

4. We can't say any $\displaystyle a$ coprime to $\displaystyle n$ .

If $\displaystyle a$ is the primitive element , we must have exactly

$\displaystyle a^{\varphi(n)} = 1$ .

However , $\displaystyle \varphi(\varphi(n) ) < \varphi(n)$ so $\displaystyle \varphi(\varphi(n) )$ cannot contain $\displaystyle \varphi(n)$and we have $\displaystyle a^{ \varphi(\varphi(n) ) } \neq 1$

For example ,

$\displaystyle 8^{ \varphi(\varphi(17)) } = 8^8 \equiv 1 \bmod{17}$

but $\displaystyle 3^8 \equiv -1 \bmod{17}$

5. Originally Posted by chiph588@
$\displaystyle b^c \bmod{\varphi(\varphi(n))} = b^c+d\varphi(\varphi(n))$ for some $\displaystyle d$

$\displaystyle a^{b^c+d\varphi(\varphi(n))}=a^{b^c}a^{d\varphi(\v arphi(n))}\equiv a^{b^c} \bmod{n}$

Since $\displaystyle (a,n)=1\implies (a^{b^c},n)=1$ so the cancelation property holds and we get $\displaystyle a^{d\varphi(\varphi(n))}\equiv1\bmod{n}$ which isn't always true.

$\displaystyle c \bmod{\varphi(\varphi(n))} = c+d\varphi(\varphi(n))$ for some $\displaystyle d$

So $\displaystyle a^{b^{c+d\varphi(\varphi(n))}} = a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{d\varphi(\varphi(n))}\equiv a^{b^c}\bmod{n}$

Therefore we require $\displaystyle d\varphi(\varphi(n))\equiv1\bmod{\phi(n)}$ or $\displaystyle a^{b^c}\equiv1\bmod{n}$; this last part is trivial though.

When $\displaystyle \varphi(n)\neq2$ we have $\displaystyle 2\mid(d\varphi(\varphi(n)),\varphi(n))$ so the above line can't have a solution.

If $\displaystyle \varphi(n)=2\implies n=3$, so we want to solve $\displaystyle d\equiv1\bmod{2}$ which we can do. Note in this case $\displaystyle d$ can be even too. This is because if $\displaystyle b=1$ the exponent doesn't matter and if $\displaystyle b=2$ then $\displaystyle \varphi(n)\mid b^c$. I'd consider $\displaystyle n=3$ to be a trivial case.

So in summary there is only one case where you're statement holds, namely $\displaystyle n=3$.

Edit: This post is also wrong. See below.

6. I don't really see where chiph588@ and simplependulum are coming from, but it seems to me that what you wrote is completely valid as long as $\displaystyle \text{gcd}(b, \varphi(n))=1$. We are merely applying Euler's theorem twice.

7. Originally Posted by undefined
I don't really see where chiph588@ and simplependulum are coming from, but it seems to me that what you wrote is completely valid as long as $\displaystyle \text{gcd}(b, \varphi(n))=1$. We are merely applying Euler's theorem twice.
Again, I made a huge mistake in my last post. My mistake came from saying $\displaystyle a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{d\varphi(\varphi(n))}$. It should read $\displaystyle a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{b^{d\varphi(\varphi(n))}}$

I then said we need $\displaystyle d\varphi(\varphi(n))\equiv1\bmod{\phi(n)}$ but what we actually need is $\displaystyle b^{d\varphi(\varphi(n))}\equiv1\bmod{\phi(n)}$

which like you said requires $\displaystyle (b,\phi(n))=1$

Two huge mistakes on one thread, how embarassing!

8. Haha looks like my question spilled a lot of virtual ink.

Thank you for your replies, with your help I managed to set up something that I can prove. Here's a nice theorem (don't know if it already exists ?) :

Let $\displaystyle \varphi_0{(n)} = n$, $\displaystyle \varphi_1{(n)} = \varphi{(n)}$, $\displaystyle \varphi_2{(n)} = \varphi{(\varphi{(n)})}$, ...

Assume $\displaystyle a_0, a_1, \cdots, a_n$ are relative numbers with the property that $\displaystyle \gcd{(a_i, \varphi_i{(n)})} = 1$ for all $\displaystyle 0 \leqslant i \leqslant n$. Then the following holds :

$\displaystyle a_0^{\left ( a_1^{\left ( a_2^{\left ( a_3^{\cdots^{( a_n + 1)} - 1} \right )} - 1 \right )} - 1 \right )} - 1 \equiv 0 \pmod{n}$

I will post the proof in some time. I do have it but it needs ... editing. It's quite simple, based on substituting zeroes modulo various $\displaystyle \varphi_i{(n)}$.

Coming back to the original question, it is indeed a matter of greatest common divisors. For instance, I can hopefully prove the original statement using a variation of my general proof:

$\displaystyle a^{\left ( b^{(c + \varphi{(\varphi{(n)})})} \right )} \equiv a^{\left ( b^c \right )} \pmod{n}$

Due to Euler's Theorem this may only work if $\displaystyle \gcd{(a, n)} = 1$. And again due to Euler's Theorem, we can write the following congruence from the statement :

$\displaystyle b^{(c + \varphi{(\varphi{(n)})})} \equiv b^c \pmod{\varphi{(n)}}$.

This, again, can only work if $\displaystyle \gcd{(b, \varphi{(n)})} = 1$. Reapplying Euler's Theorem again the following congruence is obtained :

$\displaystyle c + \varphi{(\varphi{(n)})} \equiv c \pmod{\varphi{(\varphi{(n)})}}$

With does hold for any $\displaystyle c$. Thus the original statement holds iff $\displaystyle \gcd{(a, n)} = 1$ and $\displaystyle \gcd{(b, \varphi{(n)})} = 1$.

Is this a valid proof ?

9. Originally Posted by Bacterius
Haha looks like my question spilled a lot of virtual ink.

Thank you for your replies, with your help I managed to set up something that I can prove. Here's a nice theorem (don't know if it already exists ?) :

Let $\displaystyle \varphi_0{(n)} = n$, $\displaystyle$\displaystyle \varphi_1{(n)} = \varphi{(n)}, $\displaystyle \varphi_2{(n)} = \varphi{(\varphi{(n)})}$, ...

Assume $\displaystyle a_0, a_1, \cdots, a_n$ are relative numbers with the property that $\displaystyle \gcd{(a_i, \varphi_i{(n)})} = 1$ for all $\displaystyle 0 \leqslant i \leqslant n$. Then the following holds :

$\displaystyle a_0^{\left ( a_1^{\left ( a_2^{\left ( a_3^{\left ( a_4^{\cdots^{( a_n + 1)}} - 1 \right )} - 1 \right )} - 1 \right )} - 1 \right )} - 1 \equiv 0 \pmod{n}$

I will post the proof in some time. I do have it but it needs ... editing. It's quite simple, based on substituting zeroes modulo various $\displaystyle \varphi_i{(n)}$.
I believe if you can show $\displaystyle \varphi_{n-1}(n)=1 \;\forall\; n$ then the proof is easy. What's your version of the proof?

10. This whole thread has relevance for what I'd consider a fun/beautiful problem over at Project Euler: (spoiler box contains link)

Spoiler:

I don't like giving hints that are too substantial or giving away answers, but it's such a nice tie-in I couldn't resist. Anyway, knowing that this thread is relevant doesn't make it obvious how to solve.

Just to be extra safe, I put it in a spoiler box, so that if you want, you'll only know it has relevance to one of the problems there, but not which one.

11. Originally Posted by chiph588@
I believe if you can show $\displaystyle \varphi_{n-1}(n)=1 \;\forall\; n$ then the proof is easy. What's your version of the proof?
You guys are so prompt at answering

My proof looks like this :

Originally Posted by Proof draft
Let : $\displaystyle a_i^{b_i} \equiv 1 \pmod{\varphi_i{(n)}}$ for any $\displaystyle b_i$. Euler's Theorem tells us that $\displaystyle \gcd{(a_i, \varphi_i{(n)})} = 1$ for any $\displaystyle 0 \leqslant i \leqslant n - 1$ (these become the conditions for the statement).

Then $\displaystyle b_i \equiv 0 \pmod{\varphi_{i + 1}{(n)}}$ again due to Euler's Theorem.

But the original statement is equivalent to saying that $\displaystyle b_i = a_{i + 1}^{b^{i + 1}} - 1$. Substituting :

$\displaystyle a_{i + 1}^{b^{i + 1}} - 1 \equiv 0 \pmod{\varphi_{i + 1}{(n)}}$

Or :

$\displaystyle a_{i + 1}^{b^{i + 1}} \equiv 1 \pmod{\varphi_{i + 1}{(n)}}$

Which is equivalent to what has been assumed as a condition.
The same argument is valid for any $\displaystyle 0 \leqslant i \leqslant n - 1$. Thus the statement holds assuming the original conditions.
I know this needs editing but I'm pretty sure it is a valid proof, probably formulated in a twisted way though. What do you think ?

Thanks for the link undefined, I'm bookmarking it.

12. Originally Posted by Bacterius
You guys are so prompt at answering

My proof looks like this :

I know this needs editing but I'm pretty sure it is a valid proof, probably formulated in a twisted way though. What do you think ?

Thanks for the link undefined, I'm bookmarking it.
I think with a little more work this would be valid, but I think my way would be a lot less complicated:

We know $\displaystyle \varphi_{n-1}(n)=1\implies a_{n-1}=1$, so $\displaystyle a_{n-1}^{a_n+1}-1=0$. Thus $\displaystyle a_{n-2}^0-1=0$ and we see this pattern will trickle down to $\displaystyle a_0$. So we eventually get $\displaystyle a_0^0-1$.

13. Originally Posted by chiph588@
I think with a little more work this would be valid, but I think my way would be a lot less complicated:

We know $\displaystyle \varphi_{n-1}(n)=1\implies a_{n-1}=1$, so $\displaystyle a_{n-1}^{a_n+1}-1=0$. Thus $\displaystyle a_{n-2}^0-1=0$ and we see this pattern will trickle down to $\displaystyle a_0$. So we eventually get $\displaystyle a_0^0-1$.
Clever !
I didn't think of it this way. Indeed, it is way simpler to understand (and to write in Latex as well )

Thanks