# Congruences, Powers, and Euler's Theorem

• Jan 18th 2010, 06:28 PM
ReiKon
Congruences, Powers, and Euler's Theorem
if $\displaystyle \phi$(m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence $\displaystyle a \equiv 7^{3003} \pmod{m}$

Help pls
• Jan 18th 2010, 06:33 PM
Drexel28
Quote:

Originally Posted by ReiKon
if F(m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence a = 7^3003 (mod m)

Help pls

What?? What is $\displaystyle F(m)$? I feel as though you are trying to use Euler's theorem.
• Jan 18th 2010, 06:52 PM
ReiKon
Quote:

Originally Posted by Drexel28
What?? What is $\displaystyle F(m)$? I feel as though you are trying to use Euler's theorem.

I think thats the one.

O with a line in the middle.
• Jan 18th 2010, 06:54 PM
Drexel28
Quote:

Originally Posted by ReiKon
I think thats the one.

O with a line in the middle.

$\displaystyle \phi$? Ok. So you are trying to use Euler's theorem. Do you know what it says and how to apply it?
• Jan 18th 2010, 07:01 PM
ReiKon
Quote:

Originally Posted by Drexel28
$\displaystyle \phi$? Ok. So you are trying to use Euler's theorem. Do you know what it says and how to apply it?

A bit.
• Jan 20th 2010, 02:23 AM
ReiKon
Ok, I think I found the actual answer.
Please correct me if I am wrong.

$\displaystyle a \equiv 7^{3003} \pmod{m}; \gcd (a,m)$
$\displaystyle \phi(m)=1000$
$\displaystyle m=3750$
$\displaystyle 3750=5^4\times2\times3$
$\displaystyle \phi(3750)=3750\left (1-\frac{1}{5}\right )\left (1-\frac{1}{2}\right )\left (1-\frac{1}{3}\right )$
$\displaystyle \phi(3750)=3750\left (\frac{4}{5}\right )\left (\frac{1}{2}\right )\left (\frac{2}{3}\right )$
$\displaystyle \phi(3750)=3750\left (\frac{4}{15}\right )$
$\displaystyle \phi(3750)=1000$

$\displaystyle gcd(7, 3750)$
$\displaystyle 3750 = 7 \times 535\ R\ 5$
$\displaystyle 7 = 5 \times 1\ R\ 2$
$\displaystyle 5 = 2 \times 2\ R\ 1$
$\displaystyle 2 = 1 \times 2\ R\ 0$
$\displaystyle gcd(7, 3750) = 1$

$\displaystyle 7^{\phi(m)} \equiv 1 \pmod{m}$
$\displaystyle 7^{1000} \equiv 1 \pmod{3750}$

$\displaystyle a \equiv 7^{3003} \pmod{m}$
$\displaystyle a \equiv 7^{3003} \pmod{3750}$
$\displaystyle a \equiv 7^{1000\times3+3} \pmod{3750}$
$\displaystyle a \equiv (7^{1000})^3\times7^3 \pmod{3750}$
$\displaystyle a \equiv 1\times7^3 \pmod{3750}$
$\displaystyle a \equiv 7^3 \pmod{3750}$
$\displaystyle a \equiv 343 \pmod{3750}$
$\displaystyle However,\ 343\ is\ divisible\ by\ 7.$
$\displaystyle So... a = 343 + 3750 = 4093$
$\displaystyle Which\ is\ not\ divisible\ by\ 7.$
$\displaystyle Therefore$
$\displaystyle 4093 \equiv 7^{3003} \pmod{3750}$
• Jan 20th 2010, 08:13 AM
Drexel28
Quote:

Originally Posted by ReiKon
Ok, I think I found the actual answer.
Please correct me if I am wrong.

$\displaystyle a \equiv 7^{3003} \pmod{m}; \gcd (a,m)$
$\displaystyle \phi(m)=1000$
$\displaystyle m=3750$
$\displaystyle 3750=5^4\times2\times3$
$\displaystyle \phi(3750)=3750\left (1-\frac{1}{5}\right )\left (1-\frac{1}{2}\right )\left (1-\frac{1}{3}\right )$
$\displaystyle \phi(3750)=3750\left (\frac{4}{5}\right )\left (\frac{1}{2}\right )\left (\frac{2}{3}\right )$
$\displaystyle \phi(3750)=3750\left (\frac{4}{15}\right )$
$\displaystyle \phi(3750)=1000$

$\displaystyle gcd(7, 3750)$
$\displaystyle 3750 = 7 \times 535\ R\ 5$
$\displaystyle 7 = 5 \times 1\ R\ 2$
$\displaystyle 5 = 2 \times 2\ R\ 1$
$\displaystyle 2 = 1 \times 2\ R\ 0$
$\displaystyle gcd(7, 3750) = 1$

$\displaystyle 7^{\phi(m)} \equiv 1 \pmod{m}$
$\displaystyle 7^{1000} \equiv 1 \pmod{3750}$

$\displaystyle a \equiv 7^{3003} \pmod{m}$
$\displaystyle a \equiv 7^{3003} \pmod{3750}$
$\displaystyle a \equiv 7^{1000\times3+3} \pmod{3750}$
$\displaystyle a \equiv (7^{1000})^3\times7^3 \pmod{3750}$
$\displaystyle a \equiv 1\times7^3 \pmod{3750}$
$\displaystyle a \equiv 7^3 \pmod{3750}$
$\displaystyle a \equiv 343 \pmod{3750}$
$\displaystyle However,\ 343\ is\ divisible\ by\ 7.$
$\displaystyle So... a = 343 + 3750 = 4093$
$\displaystyle Which\ is\ not\ divisible\ by\ 7.$
$\displaystyle Therefore$
$\displaystyle 4093 \equiv 7^{3003} \pmod{3750}$

What makes you so sure that $\displaystyle \phi(3750)=1000\implies m=3750$? $\displaystyle \phi(6)=2=\phi(3)$
• Jan 20th 2010, 08:28 AM
Moo
True. We have $\displaystyle \phi(2^2 \times 5^4)=\phi(3\times 5^4)=\phi(2\times 3 \times 5^4)=1000$

But I think these are the only solutions.

What's important in the fact that $\displaystyle \phi(m)=1000$ is that it's not possible that 7|m (you can do this very easily with a very short proof by contradiction). Thus gcd(7,m)=1 and we can apply Euler's theorem : $\displaystyle 7^{1000}\equiv 1 \pmod m$

And $\displaystyle 7^{3003}=(7^{1000})^3 \times 7^3 \equiv 7^3 \pmod m$

So $\displaystyle a\equiv 343 \pmod m$

And since $\displaystyle \phi(m)=1000$, it follows that $\displaystyle m>1000$.

So 343 is the number you're looking for.
• Jan 20th 2010, 08:30 AM
Drexel28
Quote:

Originally Posted by Moo
True. We have $\displaystyle \phi(2^2 \times 5^4)=\phi(3\times 5^4)=\phi(2\times 3 \times 5^4)=1000$

But I think these are the only solutions.

What's important in the fact that $\displaystyle \phi(m)=1000$ is that it's not possible that 7|m (you can do this very easily with a very short proof by contradiction). Thus gcd(7,m)=1 and we can apply Euler's theorem : $\displaystyle 7^{1000}\equiv 1 \pmod m$

And $\displaystyle 7^{3003}=(7^{1000})^3 \times 7^3 \equiv 7^3 \pmod m$

So $\displaystyle a\equiv 343 \pmod m$

And since $\displaystyle \phi(m)=1000$, it follows that $\displaystyle m>1000$.

So 343 is the number you're looking for.

Agreed!
• Jan 21st 2010, 12:41 AM
ReiKon
But 343 is divisible by 7.
$\displaystyle 343\div7=49$
• Jan 21st 2010, 02:16 AM
Moo
Yes, but I never said it wasn't. I said that m mustn't be divisible by 7.
• Jan 22nd 2010, 01:14 AM
ReiKon
Ah. I think I found the answer I was looking for.
Here it is.

$\displaystyle a \equiv 7^{3003} \pmod{m}; \gcd (a,m)$
$\displaystyle \phi(m)=1000$
$\displaystyle \phi(2^3\times5^3)=1000$
$\displaystyle \phi(\left (1-\frac{1}{2}\right )\left (1-\frac{1}{5}\right )=1000$
$\displaystyle \phi(\left (\frac{1}{2}\right )\left (\frac{4}{5}\right )=1000$
$\displaystyle \phi(\left (\frac{2}{5}\right )=1000$
$\displaystyle m=1000\times(\left (\frac{5}{2}\right )$
$\displaystyle m=2500$

$\displaystyle gcd(7, 2500)$
$\displaystyle 2500 = 7 \times 357\ R\ 1$
$\displaystyle 7 = \times 7\ R\ 0$
$\displaystyle gcd(7, 2500) = 1$

$\displaystyle 7^{\phi(m)} \equiv 1 \pmod{m}$
$\displaystyle 7^{1000} \equiv 1 \pmod{2500}$

$\displaystyle a \equiv 7^{3003} \pmod{m}$
$\displaystyle a \equiv 7^{3003} \pmod{2500}$
$\displaystyle a \equiv 7^{1000\times3+3} \pmod{2500}$
$\displaystyle a \equiv (7^{1000})^3\times7^3 \pmod{2500}$
$\displaystyle a \equiv 1\times7^3 \pmod{2500}$
$\displaystyle a \equiv 7^3 \pmod{2500}$
$\displaystyle a \equiv 343 \pmod{2500}$
$\displaystyle However,\ 343\ is\ divisible\ by\ 7.$
$\displaystyle So... a = 343 + 2500 = 2843$
$\displaystyle Which\ is\ not\ divisible\ by\ 7.$
$\displaystyle Therefore$
$\displaystyle 2843 \equiv 7^{3003} \pmod{2500}$