I'm stuck with the following question

Show that for each positive integer b,

Thank you for your help

Printable View

- March 29th 2008, 09:44 PMkleenexcongruences
I'm stuck with the following question

Show that for each positive integer b,

Thank you for your help - March 30th 2008, 12:58 AMMoo
Hello,

You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way i've found to get only elements of solution...

If you were asked to show that it had a congruence with 1 mod 1001, i would have given you Euler's theorem - March 30th 2008, 02:45 AMkleenex
- March 30th 2008, 02:49 AMMoo
Nope, it won't work :s

Because , which is not 61 o.O

Perhaps you can see what to do, if so that's good for you (Rofl) - March 30th 2008, 05:32 AMPaulRS
Well

Let

You can easily see that

whenever a is coprime to 1001

THen it follows (it is easy to prove) that

But:

THus: if a is coprime to 1001 - March 30th 2008, 06:01 AMMoo
This is the problem... You have to show it for any integer, not coprime oO

- March 30th 2008, 08:12 AMThePerfectHacker
- March 30th 2008, 08:44 AMMoo
Oh, i didn't know this thing :-) d'you have a wiki link ?

Why that :Quote:

THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001

Thanks ! - March 30th 2008, 09:01 AMThePerfectHackerQuote:

Originally Posted by**Moo**

Because,

.

Then,

.

Thus.

.

Quote:

Originally Posted by**Moo**

But it will not work for any integer. Say then (I just did it on my calculator (Tongueout) ). - March 30th 2008, 09:18 AMMoo
oO is a smiley :D

That's the problem, the initial text said that it was for any integer... I couldn't verify with my calculator, thanks

Quote:

Thus.

.

- March 30th 2008, 10:01 AMThePerfectHacker
- March 30th 2008, 10:05 AMMoo
Well,

If p & q are coprime, and x = 1 mod p and 1 mod q, why should x be = 1 mod pq ?

aaah i see, perhaps Bézout's identity could help... need to see it later - March 30th 2008, 10:07 AMThePerfectHacker
- March 30th 2008, 10:11 AMMoo
Ok, now it's all clear ! :D

Oo oO O.o o.O