NUMBER THEORY

If P is a prime and the gcd (a, p) = 1, then aP-1 = 1 mod p

 

Ex. Verify that 316 = 1 mod 17

We know: 33 = 10 (mod 17)

(33)2 = 33 = 100 = 15 (mod 17)

(36)2 = 312 = 225 = 4 (mod 17)

316 = 312 * 33 * 3 = 4 * 10 * 3 = 120 =1 mod 17

 

Ex. Verify that 186 = 1 mod 49

We know: 182 = 324 = 30 (mod 49)

(182)2 = 184 = 900 = 18 (mod 49)

(186 = 184 *182 = 18 * 30 = 1 mod 49

 

Euler's F - Function

F (n) = the # of integers < n that are relatively prime to n

F(n) = n - 1 iff n is prime

Ex.

F(20) = {1, 3, 7, 9, 11, 13, 17, 19} =8

F(7) = {1, 2, 3, 4, 5, 6} =6

 

If n = pq and p, q are prime, then F(n) = F(p) F(q) = (p - 1)(q-1)

 

Ex.

F(35) = F(7) F(5) = (7 - 1)(5 - 1) = 6 * 4 = 24

 

if p is prime and K > 0, then F(pk) = pk - pk-1 = pk-1 (p - 1)

 

Ex.

F(16) = F(24) = 23 (2 - 1) = 23 = 8 -or- F(16) = F(24) = 24 - 23 = 16 - 8 = 8

if n = p1k1 p2k2 ..... prkr

F(n) = ( p1k1 - p1k1-1)( p2k2 - p2 k2-1) ..... (prkr - pr kr-1)

 

Ex.

F(2700) = F(22) F(33) F(52)

= 2700 (1 - 1/2) (1 - 1/3) (1 - 1/5)

= 2700 (1/2) (2/3) (4/5)

= 720

 

Euler's Theorem

n >= 2 and gcd (a, n) =1, then aF(n) = 1 (mod n)

Ex.

 

-3 * -6 * -9 * -12 * -15 * -18 = 4 * 1 * 5 * 2 * 6 * 3 (mod 7)

1 (-3) * 2 (-3) * 3 (-3) * 4 (-3) * 5 (-3) * (6) (-3) = 4 * 1 * 5 * 2 * 6 * 3 (mod 7)

1 * 2 * 3 * 4 * 5 * 6 (-3)6 = 1 * 2 * 3 * 4 * 5 * 6 (mod 7)

(-3)6 = 1 (mod 7)

 

 

Chinese Remainder Theorem

 

Let n1, n2, ...... nk, be integers such that the gcd (n1, nj) = 1 for i not equal to j. Then the system of linear congruencies:

x = ar mod(nr) where r = 1, 2, ..... k. has a unique solution modulo n1, n2, ...... nk.

 

Ex.

Find the unique solution of X satisfying the system of simultaneous congruencies: x = 3(mod 5), x = 5(mod 7), x = 7(mod 11)

 

x = 3 + 5k1 = 5 (mod 7)

5k1 = 2 (mod 7)

k1 = 6 (mod 7)

= 6 + 7k2

 

x = 3 + 5(6 + 7k2)

= 3 + 30 + 35k2 = 33 + 35k2 = 7 (mod 11)

35k2 = 7 (mod 11)

k2 = 9 (mod 11)

= 9 + 11k3

 

x = 33 + 35k2

= 33 + 35k2 (9 + 11k3)(mod 11)

= 348 + 385k3 (mod 11)

 

x = 348 (mod 385)