# 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$$