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 worksheet Practise 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

Use Euclid’s algorithm to find gcd(1218, 315).

a = 1218b = 315

gcd(1218, 315) =

2.Easy

Find 509 mod 6, the remainder r with 0 ≤ r < 6.

a = 509n = 6

509 mod 6 =

3.Medium

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

n = 39 = 3·13

φ(39) =

4.Medium

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

n = 11 = 11

φ(11) =

5.Hard

79 is prime. Use Fermat’s little theorem to find 6⁷⁰¹⁶⁶ mod 79.

p = 79k = 70166

6⁷⁰¹⁶⁶ mod 79 =

6.Hard

29 is prime. Use Fermat’s little theorem to find 16⁷⁶⁸⁹² mod 29.

p = 29k = 76892

16⁷⁶⁸⁹² mod 29 =

Answer key

1. gcd(1218, 315) = 21
2. 509 mod 6 = 5
3. φ(39) = 24
4. φ(11) = 10
5. 6⁷⁰¹⁶⁶ mod 79 = 45
6. 16⁷⁶⁸⁹² mod 29 = 25

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