Mods that will rack your brain...

[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 ?

[Gokul43201]

Have you come across Fermat's Little Theorem ?

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

[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?

[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).

[1+1=1]

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

[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.

[Gokul43201]

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.

[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.

[robert Ihnot]

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.

[Gokul43201]

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.

[Gokul43201]

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.

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.

[Gokul43201]

Gokul43201

I don't know why it's sufficient to show that a^{13} \equiv a\ (\mbox{mod }n) for those n,
Post#10, line 1.

but unless a = 1 or a = 0, a cannot be congruent to a (mod 2).

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



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.

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

[Muzza]

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.


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.

[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! :biggrin:

[AKG]

What ? Any number is always congruent to itself ! Isn't 'congruence' a reflexive relation ? Isn't 0 divisible by all numbers ?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.

[robert Ihnot]

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.
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)

[robert Ihnot]

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.

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.