Homework Help: Rules of Modular Arithmetic

1. Oct 4, 2005

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?

2. Oct 4, 2005

Hurkyl

Staff Emeritus
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?

3. Oct 5, 2005

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?

4. Oct 5, 2005

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.

5. Oct 5, 2005

Hurkyl

Staff Emeritus
Yep.

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

6. Oct 5, 2005

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.

7. Oct 5, 2005

Hurkyl

Staff Emeritus
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$$