# Congruences, Powers, and Euler's Theorem

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

Help pls
• Jan 18th 2010, 07: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 $F(m)$? I feel as though you are trying to use Euler's theorem.
• Jan 18th 2010, 07:52 PM
ReiKon
Quote:

Originally Posted by Drexel28
What?? What is $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, 07:54 PM
Drexel28
Quote:

Originally Posted by ReiKon
I think thats the one.

O with a line in the middle.

$\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, 08:01 PM
ReiKon
Quote:

Originally Posted by Drexel28
$\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, 03:23 AM
ReiKon
Ok, I think I found the actual answer.
Please correct me if I am wrong.

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

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

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

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

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

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

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

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

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

What makes you so sure that $\phi(3750)=1000\implies m=3750$? $\phi(6)=2=\phi(3)$
• Jan 20th 2010, 09:28 AM
Moo
True. We have $\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 $\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 : $7^{1000}\equiv 1 \pmod m$

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

So $a\equiv 343 \pmod m$

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

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

Originally Posted by Moo
True. We have $\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 $\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 : $7^{1000}\equiv 1 \pmod m$

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

So $a\equiv 343 \pmod m$

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

So 343 is the number you're looking for.

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

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

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

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

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