Quiz 3 Lemmas/Theorems

Question 1

Diophantine equations and Modulo

Answer 1

If a Diophantine Equation has an integer solution, then it has a solution (mod m)

Question 2

What is a Modular Inverse

Answer 2

‘a’ has a modular inverse - a^-1(mod m), if there exists ‘b’ such that ab = 1(mod m). We write it as a^-1 = b(mod m)

Question 3

What is PHI(m)

Answer 3

It is the set of all number n, such that 0<= n < m such that GCD(m,n) =1

Question 4

What is phi(m)

Answer 4

It is the amount of numbers existing within PHI(m)

Question 5

Cancellation Property

Answer 5

If ab = ac(mod m) and GCD(a,m) = 1, then b = c(mod m)

Question 6

Euler’s Theorem

Answer 6

If GCD(a,m) = 1, where m is a positive integer, then a^(phi(m)) = 1(mod m)

Question 7

Fermat’s Little Theorem

Answer 7

If p is a prime and a is an integer such that p /| a, then a^(p-1) = 1(mod p)

Can use it to prove if a number is not prime

Does not prove a number is prime if it passes test, but does prove it is composite if it fails.

Question 8

Proposition about squares and moduli

Answer 8

If p is prime and a is an integer, where a^2 = 1(mod p), then a = +/-1(mod p)