# Euler's Theorem

• May 5th 2008, 02:38 PM
spoon737
Euler's Theorem
I'm supposed to prove that $a^{37} \equiv a(mod\ 1729)$ for any integer $a$ using Euler's theorem. I'm trying to first prove it under the assumption that $gcd(a, 1729)=1$, which allows me to apply Euler's theorem. In this case, I showed that $a^{\phi(1729)}=a^{1296}=(a^{36})^{36} \equiv 1(mod\ 1796)$. What I want to do is get from here to $a^{36} \equiv 1(mod\ 1796)$ so I can multiply both sides by $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, 02: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 $a^b \equiv 1 [1729] \Longrightarrow a^{b+1} \equiv a [1729]$
• May 5th 2008, 02: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, 02: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 :
$a^b \equiv 1 [1729]$ ?

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

$a^b=1729k+1$

Since d divides a, it divides $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, 03: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 $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, 03: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 $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 $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, 03: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, 05:15 PM
ThePerfectHacker
$1729 = 7\cdot 13\cdot 19$.
Let $\gcd(a,1729)=1$ then the maximal order of $a$ mod $1729$ is $\text{lcm}(\phi(7),\phi(13),\phi(19)) = \text{lcm}(6,12,18)=36$.
Also $\text{ord}(a) | \phi(1729) = 36^2$. Combining these two results we get that $\text{ord}(a) | 36$.
This immediately tells us that $a^{36} \equiv 1(\bmod 1729)$.
Multiply both sides by $a$: $a^{37}\equiv a(\bmod 1729)$.

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

Say that $\gcd(a,1729)\not = 1$ this means $7|a$ or $13|a$ or $17|a$.
Say that $7|a$ but not the other factors, i.e. $a=7b$ and $\gcd(b,1729) = 1$.
Then, $a^{37} \equiv a (\bmod 1729) \implies 7^{37}b^{37}\equiv 7 b(\bmod 1729)$.
But $b^{37}\equiv b(\bmod 1729)$ by above argument.
Thus, we are left with $7^{37}\equiv 7(\bmod 1729)$.
This is of course true.
The same argument when $13|a$ and $19|a$.
• May 5th 2008, 05: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 $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 :
$a^b \equiv 1 [1729]$ ?

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

$a^b=1729k+1$

Since d divides a, it divides $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 $a^{36}\equiv 1(\bmod 1729)$. This means $\gcd(a^{36},1729) = \gcd(1,1729) = 1$ (because they are the same under the same modulos). Thus, $\gcd(a,1729)\not = 1$ which is a problem.