What is the theorem about modulos and relatively prime numbers?

[Icebreaker]

Is it possible to manipulate and substitute modulos like so

a^5 = a (mod 5)
a^3 = a (mod 3)

a^15 = a (mod 15)

By substituting the first into the second?

 

[Hurkyl]

It helps to fall back on the definitions...

Recall that a^5 = a (mod 5) means 5 | (a^5 - a).
Similarly, a^3 = a (mod 3) means 3 | (a^3 - a).

Now that the problem's converted into ordinary arithmetic, can you figure anything out?

 

[murshid_islam]

so 15 | (a^5 - a)(a^3 - a)
or 15 | a^8 - a^6 - a^4 + a^2

is that what you mean, Hurkyl?

 

[Icebreaker]

a^p (mod n) as a increases or as p increases is cyclic, is it not? I think I can answer my question using this property.

 

[Hurkyl]

is that what you mean, Hurkyl?

Yep.

a^p (mod n) as a increases or as p increases is cyclic, is it not? I think I can answer my question using this property.

Huh? I'm not sure if you're getting there or not...

 

[Icebreaker]

Mmm, I thought I needed this property to prove another theorem, but it seems I was wrong. I'll try to do it anyway though:

5n = a^5-a
3k = a^3-a

5n-3k = a^5-a^3 = a^2(a^3-a)

I'll try to finish later.

 

[Hurkyl]

Here's another way of looking at it: if a^15 = a (mod 15), then you have a = a^15 = (a^3)^5 = a^5 (mod 3). Do you think a = a^5 (mod 3)?

Now you do have this nifty theorem:

If m and n are relatively prime, then:

$$m^{\phi(n)} = 1 \mod n$$