Check out some similar questions!

mmangiapane · Oct 29, 2006, 12:47 PM

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

Frank Choe · Dec 11, 2006, 08:41 AM

How could a be divisible by 9, but not divisible by 3? Do you mean that a is divisible by 9 only such as a = 9*n? Maybe what you meant was a = 9*(3*m+1 or 2), which is still divisible by 3, but the quotient is not divisible by 3?

Capuchin · Dec 13, 2006, 07:14 AM

I think it was an OR statement, Either not divisible by three or divisible by 9

asterisk_man · Dec 13, 2006, 08:20 AM

what's the conclusion?
Frank's interpretation:
a is an integer such that (a mod 3 != 0) and (a mod 9 = 0)
this set is clearly empty
Capuchin's interpretation:
a is an integer such that (a mod 3 != 0) or (a mod 9 = 0)
this set is all integers except multiples of 3 which are not multiples of 9

I think I agree with Capuchin. The way it starts I would expect to use Frank's interpretation but when I look at the exact wording I agree with Capuchin.

and to be clear, whatever the set, are we trying to show that a^7 mod 63 = a?

Frank Choe · Dec 15, 2006, 09:03 PM

If I express it in an equation form, the problem appears as follows:

a^7 (mod 63) = a

if and only if a=(3*n +/- 1) where n=1, 2,3,. OR
if and only if a=9*n.

Empirically I can see that it is true. To provide a mathematical proof, someone has to do a lot of work, devising logical steps. I wonder what the results would be for cases when a=27*n or 81*n. Is this somehow related to Fermat's Second Lemma? This sounds like a tough problem proof-wise.