Number theory & modular arithmetic worksheet with answers

Free printable Number theory & modular arithmetic worksheet: 6 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy
aqbr645=?·405+??=?·?+??=?·?+??=?·?+??=?·?+?

Use Euclid’s algorithm to find gcd(645, 405).

a = 645b = 405
gcd(645, 405) =
2.Easy

Find 829² mod 5 without multiplying out the large numbers: reduce first.

n = 5
829² mod 5 =
3.Medium

Find Euler’s totient φ(845), the number of integers from 1 to 845 that are coprime to 845.

n = 845 = 5·132
φ(845) =
4.Medium

Find the inverse of 16 modulo 71: the number x with 0 < x < 71 and 16·x ≡ 1 (mod 71).

a = 16n = 71
16−1 mod 71 =
5.Hard

73 is prime. Use Fermat’s little theorem to find 653431 mod 73.

p = 73k = 53431
653431 mod 73 =
6.Hard
mc = me​ mod n176m = cd​ mod n?(n, e) = (481, 23)d

An RSA key uses p = 13, q = 37 and e = 23. Decrypt the ciphertext c = 176: find the message m.

p = 13q = 37e = 23c = 176
m =

Answer key

  1. 1. gcd(645, 405) = 15
  2. 2. 829² mod 5 = 1
  3. 3. φ(845) = 624
  4. 4. 16−1 mod 71 = 40
  5. 5. 653431 mod 73 = 54
  6. 6. m = 67

Full step-by-step solutions: practise this topic on examproblems.com.