Euler Totient Function Question

**Bacterius** · June 2nd 2010, 08:02 PM

Hello,
I just need to know if this holds :

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

I know this is true but what about this :

$ a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n} $ For any $a$ coprime with $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

**undefined** · June 2nd 2010, 08:10 PM

Originally Posted by Bacterius

Hello,
I just need to know if this holds :

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

I know this is true but what about this :

$ a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n} $ For any $a$ coprime with $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 $\text{gcd}(b, \varphi(n))=1$ ?

**chiph588@** · June 2nd 2010, 08:12 PM

Originally Posted by Bacterius

Hello,
I just need to know if this holds :

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

I know this is true but what about this :

$ a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n} $ For any $a$ coprime with $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

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

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

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

Edit: I read your question wrong... hold on for a bit

**simplependulum** · June 2nd 2010, 08:26 PM

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

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

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

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

For example ,

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

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

**chiph588@** · June 2nd 2010, 08:33 PM

Originally Posted by chiph588@

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

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

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

Edit: I read your question wrong... hold on for a bit

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

So $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 $d\varphi(\varphi(n))\equiv1\bmod{\phi(n)}$ or $a^{b^c}\equiv1\bmod{n}$ ; this last part is trivial though.

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

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

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

Edit: This post is also wrong. See below.

**undefined** · June 2nd 2010, 08:55 PM

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 $\text{gcd}(b, \varphi(n))=1$ . We are merely applying Euler's theorem twice.

**chiph588@** · June 2nd 2010, 09:06 PM

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 $\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 $a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{d\varphi(\varphi(n))}$ . It should read $a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{b^{d\varphi(\varphi(n))}}$

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

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

Two huge mistakes on one thread, how embarassing!

**Bacterius** · June 3rd 2010, 12:57 PM

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 $\varphi_0{(n)} = n$ , $\varphi_1{(n)} = \varphi{(n)}$ , $\varphi_2{(n)} = \varphi{(\varphi{(n)})}$ , ...

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

$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 $\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:

$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 $\gcd{(a, n)} = 1$ . And again due to Euler's Theorem, we can write the following congruence from the statement :

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

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

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

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

Is this a valid proof ?

**chiph588@** · June 3rd 2010, 01:28 PM

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 $\varphi_0{(n)} = n$ , $<html> <head> <style type=$ img.top {vertical-align:15%;} $\varphi_1{(n)} = \varphi{(n)}$ " alt=" $\varphi_1{(n)} = \varphi{(n)}$ " />, $\varphi_2{(n)} = \varphi{(\varphi{(n)})}$ , ...

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

$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 $\varphi_i{(n)}$ .

I believe if you can show $\varphi_{n-1}(n)=1 \;\forall\; n$ then the proof is easy. What's your version of the proof?

**undefined** · June 3rd 2010, 01:38 PM

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.

**Bacterius** · June 3rd 2010, 01:59 PM

Originally Posted by chiph588@

I believe if you can show $\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 : $a_i^{b_i} \equiv 1 \pmod{\varphi_i{(n)}}$ for any $b_i$ . Euler's Theorem tells us that $\gcd{(a_i, \varphi_i{(n)})} = 1$ for any $0 \leqslant i \leqslant n - 1$ (these become the conditions for the statement).

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

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

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

Or :

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

**chiph588@** · June 3rd 2010, 02:16 PM

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 $\varphi_{n-1}(n)=1\implies a_{n-1}=1$ , so $a_{n-1}^{a_n+1}-1=0$ . Thus $a_{n-2}^0-1=0$ and we see this pattern will trickle down to $a_0$ . So we eventually get $a_0^0-1$ .

**Bacterius** · June 3rd 2010, 02:52 PM

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 $\varphi_{n-1}(n)=1\implies a_{n-1}=1$ , so $a_{n-1}^{a_n+1}-1=0$ . Thus $a_{n-2}^0-1=0$ and we see this pattern will trickle down to $a_0$ . So we eventually get $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

Thread: Euler Totient Function Question

LinkBack

Thread Tools

Display

Euler Totient Function Question

Similar Math Help Forum Discussions

Euler's totient function

Euler Totient Function

Euler totient function

Euler's Totient Function

Euler totient function

Search Tags