# fermat,euler,or CRT?

• Jan 4th 2008, 07:51 AM
yellow4321
fermat,euler,or CRT?
.
>
• Jan 4th 2008, 08:44 AM
yellow4321
.
>
.
• Jan 4th 2008, 10:20 AM
PaulRS
Well 37 is prime, thus: $7^{36}\equiv{1}(\bmod.37)$ (Fermat's little theorem)

$7^{25}\equiv{z}(\bmod.36)$ with $0\leq{z}<36$

Thus: $7^{7^{25}}=7^{36k+z}\equiv{7^{z}}(\bmod.37)$ where k is a natural number

We shall now find $z$

Note that $\phi(36)=12$ thus by Euler's Theorem: $7^{12}\equiv{1}(\bmod.36)$ and (squaring) $7^{24}\equiv{1}(\bmod.36)$

So: $7^{25}\equiv{7}(\bmod.36)$ and $z=7$

We finally get that: $7^{7^{25}}\equiv{7^7}(\bmod.37)$ (Whew)
• Jan 4th 2008, 10:37 AM
Isomorphism
For the order of 17, you might be tempted to try Euler's theorem, but it will not give you an answer. However it will let you narrow your search. Then you can kill the problem by case wise analysis.
What I mean is:
Indeed $17^{\phi(27)} \equiv 1 \mod 27 \Rightarrow 17^{18} \equiv 1 \mod 27$
But this only says the order divides 18. So it can be any element from the set {2,3,6,9,18}.
Try all these possibilities in the increasing order and you will get 6 as the answer.
• Jan 4th 2008, 10:47 AM
yellow4321
pure genius
• Jan 4th 2008, 02:08 PM
galactus
Sorry about my first post. Doubt if it was much help. I was in a hurry and got to thinking of someting else. Anyway:

Here's one way I got to looking at.

There are 9 non zero modulo 37 residues. So we must figure out where $7^{25}$ lies in this repeating chain of remainders.

$7^{0}\equiv{1}(mod \;\ 37)$

$7^{1}\equiv{7}(mod \;\ 37)$

$7^{2}\equiv{12}(mod \;\ 37)$

$7^{3}\equiv{10}(mod \;\ 37)$

$7^{4}\equiv{33}(mod \;\ 37)$

$7^{5}\equiv{9}(mod \;\ 37)$

$7^{6}\equiv{26}(mod \;\ 37)$

$7^{7}\equiv{34}(mod \;\ 37)$

$7^{8}\equiv{16}(mod \;\ 37)$

Then they repeat.

But, $7^{25}\equiv{7}(mod \;\ 9)$

That means $7^{25}$ is 7 more than a multiple of 9.

So, we count up the residues and see we light at a remainder of 34.

Another thing we may be able to do is since $7^{9}\equiv{1}(mod \;\ 37)$, we can break $7^{25}$ into as many powers of $7^{9}$ as possible.

$7^{25}=7^{7}\cdot{7^{18}}=7^{7}(7^{9})^{2}=7^{7}(1 )^{2}=7^{7}\equiv{34}(mod \;\ 37)$