# Euler's Theorem

• May 5th 2008, 01:38 PM
spoon737
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.
• May 5th 2008, 01:42 PM
Moo
Hello,

Quote:

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]$
• May 5th 2008, 01:50 PM
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?
• May 5th 2008, 01:56 PM
Moo
Quote:

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 ? :)
• May 5th 2008, 02:05 PM
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?

Also, any help with the first part of my post would be greatly appreciated as well.
• May 5th 2008, 02:10 PM
Moo
Quote:

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...
• May 5th 2008, 02:14 PM
spoon737
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.
• May 5th 2008, 04:15 PM
ThePerfectHacker
$\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$.
• May 5th 2008, 04:19 PM
ThePerfectHacker
Quote:

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

Quote:

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.