Number Theory and its Applications

8 Primitive Roots

“The mathematician Pascal admires the beauty of a theorem in number theory; it’s as though he were admiring a beautiful natural phenomenon. Its marvellous, he says, what wonderful properties numbers have. It’s as though he were admiring the regularities in a kind of crystal.”

– Ludwig Wittgenstein

8.1 Introduction

In this chapter we have studied another important aspect of modular arithmetic called primitive root. To study primitive roots we have introduced the concept of order of an integer modulo k(∈ ℝ⁺). The order of an integer a modulo k is the least positive integer t for which a^t ≡ 1(mod k), where gcd(a, k) = 1. Basically for this value of k, a becomes the primitive root of k if t becomes ϕ(k). For instance 3 is a ...