# Mods that will rack your brain

1. Jul 3, 2004

### 1+1=1

show that a^13 is congruent to a (modulo 2730)

if a is an integer such that a is not divisidble by 3, or such that a IS divisible by 9, then a^7 is congruent to a (mod 63)

with these, could i just divide the mod numbers by the powers? that is what i am doing, but it seems like as though it ISN'T right... anyone help ?

2. Jul 4, 2004

### Gokul43201

Staff Emeritus
Have you come across Fermat's Little Theorem ?

a^p == a (mod p) for prime p

3. Jul 4, 2004

### 1+1=1

gokul, could i say that b/c of fermat's thm, i can say that it IS == to a, because of the fact that 13 is prime? would i need to prove any further? also, could that work for the second one? anyone else think so?

4. Jul 4, 2004

### AKG

What exactly are you asking? According to that theorem

a^13 = a (mod 13), but you need to show a^13 = a (mod 2730), so of course you need to prove more! I've never taken any courses on number theory, but you might know a theorem that takes advantage of the fact that 2730 = 0 (mod 13).

5. Jul 4, 2004

### 1+1=1

ok so i could set it up, then say, "according to fermat's theorem,... and apply the theorem to this probloem?

6. Jul 4, 2004

### AKG

Uhh.. are you asking if you're allowed to use Fermat's Little Theorem? I suppose you should ask your teacher/prof/t.a.

7. Jul 4, 2004

### Gokul43201

Staff Emeritus
I haven't taken any courses either...but this is what I would do. The folks that really know some number theory probably have a far better approach.

2730 = 13*7*5*3*2
So we are done if we can show that a^13 == a (mod n), for n=2,3,5,7, and 13.
Use both forms of the Little Theorem...
a^p == a (mod p), for all prime p and a^(p-1) == 1 (mod p) for prime p, when p does not divide a.

Clearly a^13 == a (mod 13) ---- (1)

Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

Again, a^5 == a (mod 5)
and a^4 == 1 (mod 5) => a^8 == 1 (mod 5)
Hence a^13 == a (mod 5) ---(3)

Likewise, show this for n=3 and n=2..and you are done.

This proof lacks some rigor (in that, for each result, the exceptions need to be covered. This is not hard at all), but I'm going to leave that to you to find and fill in.

Last edited: Jul 5, 2004
8. Jul 4, 2004

### AKG

Gokul43201

I don't know why it's sufficient to show that $a^{13} \equiv a\ (\mbox{mod }n)$ for those n, but unless a = 1 or a = 0, a cannot be congruent to a (mod 2).

1+1=1

For your second question, part of it is easy:

To prove $a^7 \equiv a\ (\mbox{mod }63)$ if a is divisible by 9, we can start by saying:

$$a^7 \equiv a\ (\mbox{mod }7)$$

Therefore, for some integer x:

$$a^7 = 7x + a$$

Now, since a is a multiple of 9, $a^7$ must also be a multiple of 9, and thus 7x must also be a multiple of 9. So, for some integer y, x = 9y. Now, we have:

$$a^7 = 63y + a$$

I think this is sufficient to prove $a^7 \equiv a\ (\mbox{mod }63)$ if a is divisible by 9.

Last edited: Jul 4, 2004
9. Jul 4, 2004

### robert Ihnot

No dividing by 0

Much of the work on the problem is good, but remember that we can not divide by 0. For that reason forget about a^p ==a implies a^(p-1) ==1. That is not true in general. For example in the case of a^13 = =a Mod 7, we have a^13 =a^7 x a^6 ==a x a^6 == a^7 ==a Mod 7, this is true even for a=7. The arithmetic is 7^7 ==7==0 Mod 7, but 7^6 ==0 Mod7 also, not 1.

Last edited: Jul 4, 2004
10. Jul 4, 2004

### Gokul43201

Staff Emeritus
If a==b (mod n) and a==b (mod m), then a==b (mod mn), if gcd(m,n)=1.

AND

If n divides a, ie. if a==0 (mod n), then clearly a^k == 0 (mod n), which implies that a^k==a (mod n).

I think I've said too much already.

Last edited: Jul 5, 2004
11. Jul 5, 2004

### Gokul43201

Staff Emeritus
I'm not sure if this is directed at me...

I insist that nothing I have said is wrong, and that I do not carelessly divide congruence relations. Please re-read what I have written.

12. Jul 5, 2004

### Gokul43201

Staff Emeritus
Post#10, line 1.

What ? Any number is always congruent to itself ! Isn't 'congruence' a reflexive relation ? Isn't 0 divisible by all numbers ?

This looks okay. But there's a shorter way...see post#10.

Last edited: Jul 5, 2004
13. Jul 5, 2004

### Muzza

No, it's not true in general, but it IS true when p is prime and p doesn't divide a (i.e a != 0 (mod p)). Besides, Gokul43201 was talking about modulo p, so your counterexample doesn't hold.

Last edited: Jul 5, 2004
14. Jul 5, 2004

### 1+1=1

first of all, thank you to all who helped with the input! i too figured some of it out on my own, but with this it reinforced what i had! isn't that what learning is about, doing some on your own then seeing what others have? i wish i could meet you all and thank yall in person!

15. Jul 5, 2004

### AKG

Oh, you're right. I was thinking that a (mod 2) didn't work if a > 2, I thought 17 (mod 4) would be wrong, and 1 (mod 4) would be the right way to do it, but I suppose they're both right, I've just never seen "17 (mod 4)" or "a (mod 2)" [for a > 2] before.

16. Jul 5, 2004

### robert Ihnot

I thought you said, I took it from what you wrote:

This what you wrote:
Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

17. Jul 5, 2004

### robert Ihnot

the fact of the problem

You said, Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

Here we really want X^13 ==X Mod 2730, so I thought from how I read you that you were not considering X =7,14,21...etc. That is how I thought about it.