if (m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence

Help pls

Printable View

- Jan 18th 2010, 06:28 PMReiKonCongruences, Powers, and Euler's Theorem
if (m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence

Help pls - Jan 18th 2010, 06:33 PMDrexel28
- Jan 18th 2010, 06:52 PMReiKon
- Jan 18th 2010, 06:54 PMDrexel28
- Jan 18th 2010, 07:01 PMReiKon
- Jan 20th 2010, 02:23 AMReiKon
Ok, I think I found the actual answer.

Please correct me if I am wrong.

- Jan 20th 2010, 08:13 AMDrexel28
- Jan 20th 2010, 08:28 AMMoo
True. We have

But I think these are the only solutions.

What's important in the fact that 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 :

And

So

And since , it follows that .

So 343 is the number you're looking for. - Jan 20th 2010, 08:30 AMDrexel28
- Jan 21st 2010, 12:41 AMReiKon
But 343 is divisible by 7.

- Jan 21st 2010, 02:16 AMMoo
Yes, but I never said it wasn't. I said that

**m**mustn't be divisible by 7. - Jan 22nd 2010, 01:14 AMReiKon
Ah. I think I found the answer I was looking for.

Here it is.