# Thread: Euler's Theorem

1. ## Euler's Theorem

I'm supposed to prove that $\displaystyle a^{37} \equiv a(mod\ 1729)$ for any integer $\displaystyle a$ using Euler's theorem. I'm trying to first prove it under the assumption that $\displaystyle gcd(a, 1729)=1$, which allows me to apply Euler's theorem. In this case, I showed that $\displaystyle a^{\phi(1729)}=a^{1296}=(a^{36})^{36} \equiv 1(mod\ 1796)$. What I want to do is get from here to $\displaystyle a^{36} \equiv 1(mod\ 1796)$ so I can multiply both sides by $\displaystyle a$ and get the result. However, I'm not sure how to fill in that gap. Is there some theorem I can use? Or am I going about this in the wrong way?

Also, I'm not sure how to handle the case where a and 1729 are not relatively prime. Any help there would be appreciated as well.

2. Hello,

Also, I'm not sure how to handle the case where a and 1729 are not relatively prime.
If a is not coprime with 1729, this means that a doesn't belong to the invertible group of Z/1729Z. So there doesn't exist b such as $\displaystyle a^b \equiv 1 [1729] \Longrightarrow a^{b+1} \equiv a [1729]$

3. Thanks for the reply, but this is for an elementary number theory course. I can't use any group theory. Is there a different way I can handle that case?

4. Originally Posted by spoon737
Thanks for the reply, but this is for an elementary number theory course. I can't use any group theory. Is there a different way I can handle that case?
Hm...

Let a be a non-coprime number with 1729. Therefore, there is a common factor d, different from 1.

Is there b such as :
$\displaystyle a^b \equiv 1 [1729]$ ?

If so, we know that $\displaystyle a^b-1$ is a multiple of 1729 : $\displaystyle a^b-1=1729k$, $\displaystyle k \in \mathbb{Z}$

$\displaystyle a^b=1729k+1$

Since d divides a, it divides $\displaystyle a^b$. And it divides 1729 too. So it has to divide 1 too, which is not possible unless d=1 -> contradiction.

Is it better this way ?

5. Okay, that's definitely within the scope of the material I know, but I'm not sure how it relates to what I'm trying to prove. I need to show that $\displaystyle a^{37} \equiv a(mod\ 1729)$ for any integer a. The last part of my original post is asking how to show this when a and 1729 aren't coprime. Perhaps I'm just not seeing the connection?

Also, any help with the first part of my post would be greatly appreciated as well.

6. Originally Posted by spoon737
Okay, that's definitely within the scope of the material I know, but I'm not sure how it relates to what I'm trying to prove. I need to show that $\displaystyle a^{37} \equiv a(mod\ 1729)$ for any integer a. The last part of my original post is asking how to show this when a and 1729 aren't coprime. Perhaps I'm just not seeing the connection?
I think I showed you couldn't find any power of a such as $\displaystyle a^b \equiv a [1729]$ if a and 1729 aren't coprime.

I'm quite tired and I can't help with the first part, sorry...

7. Hmm, that's strange. According to my book, it should be true for all integers, whether a and 1729 are coprime or not. I just thought it would be easiest to prove it in both cases.

Thanks for your input, though, I really appreciate the help.

8. $\displaystyle 1729 = 7\cdot 13\cdot 19$.
Let $\displaystyle \gcd(a,1729)=1$ then the maximal order of $\displaystyle a$ mod $\displaystyle 1729$ is $\displaystyle \text{lcm}(\phi(7),\phi(13),\phi(19)) = \text{lcm}(6,12,18)=36$.
Also $\displaystyle \text{ord}(a) | \phi(1729) = 36^2$. Combining these two results we get that $\displaystyle \text{ord}(a) | 36$.
This immediately tells us that $\displaystyle a^{36} \equiv 1(\bmod 1729)$.
Multiply both sides by $\displaystyle a$: $\displaystyle a^{37}\equiv a(\bmod 1729)$.

The next step is to argue that: $\displaystyle 7^{36}\equiv 1(\bmod 13\cdot 19)$, $\displaystyle 13^{36}\equiv 1(\bmod 7\cdot 19)$, $\displaystyle 19^{36}\equiv 1(\bmod 7\cdot 13)$.
We will prove the first case, the other two are similar.
Note $\displaystyle \gcd(7,13\cdot 19)=1$ and maximal order of $\displaystyle a$ mod $\displaystyle 13\cdot 19$ is $\displaystyle \text{lcm}(\phi(13),\phi(19)) = 36$.
Using a similar argument as in the first paragraph we can get $\displaystyle 7^{36}\equiv 1(\bmod 13\cdot 19)$.
This tells us that: $\displaystyle 7^{37}\equiv 7, 13^{37}\equiv 13, 19^{37}\equiv 19(\bmod 1729)$.

Say that $\displaystyle \gcd(a,1729)\not = 1$ this means $\displaystyle 7|a$ or $\displaystyle 13|a$ or $\displaystyle 17|a$.
Say that $\displaystyle 7|a$ but not the other factors, i.e. $\displaystyle a=7b$ and $\displaystyle \gcd(b,1729) = 1$.
Then, $\displaystyle a^{37} \equiv a (\bmod 1729) \implies 7^{37}b^{37}\equiv 7 b(\bmod 1729)$.
But $\displaystyle b^{37}\equiv b(\bmod 1729)$ by above argument.
Thus, we are left with $\displaystyle 7^{37}\equiv 7(\bmod 1729)$.
This is of course true.
The same argument when $\displaystyle 13|a$ and $\displaystyle 19|a$.

9. Originally Posted by Moo
Hello,

If a is not coprime with 1729, this means that a doesn't belong to the invertible group of Z/1729Z. So there doesn't exist b such as $\displaystyle a^b \equiv 1 [1729] \Longrightarrow a^{b+1} \equiv a [1729]$
Originally Posted by Moo
Hm...

Let a be a non-coprime number with 1729. Therefore, there is a common factor d, different from 1.

Is there b such as :
$\displaystyle a^b \equiv 1 [1729]$ ?

If so, we know that $\displaystyle a^b-1$ is a multiple of 1729 : $\displaystyle a^b-1=1729k$, $\displaystyle k \in \mathbb{Z}$

$\displaystyle a^b=1729k+1$

Since d divides a, it divides $\displaystyle a^b$. And it divides 1729 too. So it has to divide 1 too, which is not possible unless d=1 -> contradiction.

Is it better this way ?
Here is another way.
Say that $\displaystyle a^{36}\equiv 1(\bmod 1729)$. This means $\displaystyle \gcd(a^{36},1729) = \gcd(1,1729) = 1$ (because they are the same under the same modulos). Thus, $\displaystyle \gcd(a,1729)\not = 1$ which is a problem.