(programming required) Implicitly, the Fermat–Euler theorem gives a different way to compute the multiplicative inverse of a in Zn: 1. compute ϕ(n) [say by brute force, though there are somewhat...

(programming required) Implicitly, the Fermat–Euler theorem gives a different way to compute the multiplicative inverse of a in Z_n:

1. compute ϕ(n) [say by brute force, though there are somewhat faster ways—see Exercises 9.34–9.36]; and

2. compute a ϕ(n)−1 mod n [perhaps using repeated squaring; see Figure 7.7].