Hint for Number Theory homework

1) find the pattern of the following:
a) (3^10) modulo 11
b) (2^12) modulo 13
c) (5^16) modulo 17
d) (3^22) modulo 23
2) Propose a theorem

I found the answer:
1) It is all 1
2) The theorem is as following:
(a^(n-1) modulo n) = 1; where n is prime;
n = 3 and a 0

There is not proof required for homework;
But I want to prove the theorem; but I am stuck
since induction does not seem to work due to
variance nature of n; any hint. Thanks.
KingGeorge is needed. Thanks. Regards.

Question

Hint for Number Theory homework

1) find the pattern of the following:
     a) (3^10) modulo 11
     b) (2^12) modulo 13
     c) (5^16) modulo 17
     d) (3^22) modulo 23
  2) Propose a theorem

I found the answer:
   1) It is all 1
   2) The theorem is as following:
        (a^(n-1) modulo n) = 1; where n is prime; 
                                               n >= 3 and a > 0

There is not proof required for homework;
  But I want to prove the theorem; but I am stuck
  since induction does not seem to work due to
  variance nature of n; any hint. Thanks.
  KingGeorge is needed. Thanks. Regards.

amistre64 · Answer

it has possibly to do with relatively prime stuff

amistre64 · Answer

if p and q are prime, then p mod q = p

p^(q-1) mod q

p^(q) p^(-1) mod q

p^q mod q = 1,  proof it?

amistre64 · Answer

king george might be more elegant, i agree :)

anonymous · Answer

Hi Amistre64,
   Thanks a lot for your hints. In my proposed theorem, "a" does not have to be
   prime and it is still works. (9^16 modulo 17)=1. So does the hint still apply?
   I just started the course about 2 week ago and King George was the first to
   help. More elegance is more better. Thanks again Amistre64.

amistre64 · Answer

in the examples provided, they used primes.

you will notice that 9 and 17 are relatively prime,  meaning that their gcd is 1

anonymous · Answer

Hi Amistre64,
   Maybe, "a" is prime will work for all cases. "a" including non-prime might work only
   occasionally. Hence my proposed theorm is wrong. Thanks.

amistre64 · Answer

4^7 mod 8 = 0

anonymous · Answer

Hi Amistry64,
   It is a^(n-1) modulo n; where: n is prime. in your case 8 is not prime. I am missing
   something. Thanks again.

amistre64 · Answer

itll only work out if gcd(a,n) = 1

fermats little thrm is:  a^(p-1) = 1 mod p,  as long as p does not divide a

theres proofs for that

anonymous · Answer

Hi Amistry64,
   Thanks And I noticed the "a" to be prime in the sample; However, I checked out
   non-prime as well. So I made my proposed to be non-prime as well. It is risky;
   but more general; hence I need to prove before commit. Thanks.

anonymous · Answer

Hi Amistry64,
   Thanks and great stuff; I am not aware of "little" theorem as yet;
   So I can proposed: gcd (a, p) = 1 for general case. Thanks.

amistre64 · Answer

consider a and n, such that they are relatviely prime:

the set:  a,2a,3a,4a,...,(n-1)a, none of which are divisible by n

then the construct:  a*2a*3a*4a*...*(n-1)a is equal to a^(n-1)

a*2a*3a*4a*...*(n-1)a = 1*2*3*4*...*(n-1) (mod n)

a^(n-1) = (n-1)!  (mod n)

it stands to reason that any multiple of a^(n-1) is also congruent (n-1)!  mod n

therefore

a^(n-1) * (n-1)! = (n-1)!  (mod n)

since the gcd(n, (n-1)!) = 1  we can divide out the (n-1)!

a^(n-1) = 1  (mod n)

amistre64 · Answer

this might only hold of n is prime

anonymous · Answer

Hi Amistre64,
   Sorry for misspelling (Amistry64). :-) :-) :-)

   Thanks a lot for your answer; I will try not to see your answer; I need to try it for myself
   first; So I guess, the hints you gave is enough??? Thanks.

amistre64 · Answer

they are sufficient yes :)  and good luck

anonymous · Answer

Thanks again. Best regards.