P2L5.5: Modular Arithmetic

Question 1

What is the formula for mod’ing a negative number?

Answer 1

A mod B
A = Q * B + R
Q = floor(A/B)

Question 2

• What is -6 mod 18?

Answer 2

A = Q * B + R
Q = floor(-6/18) ==> -(1/3) ==> -1 (round down!)
-6 = -1 * 18 + R

12 = R

Question 3

• What is -17 mod 7?

Answer 3

A = Q * B + R
Q = floor(-17/7) ==> -(2.4) ==> -3 (round down!)
-17 = -3 * 7 + R

4 = R

Question 4

What does the Property of Congruence say about…

A = B mod C

Answer 4

A mod C = B mod C

Question 5

What are the steps to calculate a Modular Inverse?

Answer 5

Step 1: Calculate A*B mod C for B equal to values 0 through (C-1)
Step 2: Modular inverse of A mod C is the B value that makes AB mod C = 1

Question 6

Find the modular inverse of 8 mod 5.

Answer 6

• Calculate A*B mod C for B equal to values 0 through C-1
  
  • 8*0 mod 5 = 0
  • 8*1 mod 5 = 3
  • 8*2 mod 5 = 1

Question 7

How do you tell if two numbers are relatively prime?

Answer 7

Their greatest common factor should be 1

Question 8

Are 6 and 8 relatively prime?

Answer 8

No, because…
[1, 2, 3, 6] and [1, 2, 4, 8]
have 2 as their greatest/highest common factor.

Question 9

Are 6 and 35 relatively prime?

Answer 9

Yes, because…
[1, 2, 3, 6] and [1, 5, 7, 35]
have 1 as their greatest/highest common factor.

Question 10

How do you tell if a number is a prime root of another number?

Answer 10

If we are checking to see if A is a prime root of B, then take A and calculate…
A^0 mod B = W
A^1 mod B = X
A^2 mod B = Y
A^B-1 mod B = Z
If W through Z are all unique then A is a prime root of B.

Question 11

Is 2 a prime root of 7?

Answer 11

YES, because...
* 2^1 mod 11 = 2
* 2^2 mod 11 = 4
* 2^3 mod 11 = 8
* 2^4 mod 11 = 5
* 2^5 mod 11 = 10
* 2^6 mod 11 = 9
* 2^7 mod 11 = 7
* 2^8 mod 11 = 3
* 2^9 mod 11 = 6
* 2^10 mod 11 = 1
All numbers are unique so 2 is a prime root of 11.