Number theory 12
Prepared Rashmi
Presented and content edited by Nandakumar
Determination of Integers having Primitive Roots
OBJECTIVES
- familiarize to determine integers having primitive roots
- understands the concept of indices
Introduction
In this session we discuss about integers having primitive roots . That is here we characterize all integers that have primitive roots belonging to them.also the concept of indices.
Lemma 1. Let a be any odd integer. Then
Proof: To prove, we use induction on n. Suppose n=3. We must prove that
a21 (mod 8)………………..(1)
Since a is odd, a is congruent to either 1, 3, 5 or 7 (mod 8). Therefore a2 is congruent to 1 (mod 8). Hence (1) holds.
Now suppose that the statement holds for n=k≥ 3, i.e. if a is an odd integer then……(9)
Consider
Since (2) holds, there is an integer such that
As k 3 k > 2 k-1>1.
Therefore
Or
Hence we have
Theorem1 :there are no primitive roots belonging to 2n for every
Lemma2: Let m ,n each>2 be any integers and (m,n)=1.then there exits no primitive roots (mod mn).
Corollary 1: If n is an integer either of the form pk ql p, q distinct odd primes and integers k, l 1 or of the form 4pk, p an odd prime and integer k 1,
then there exist no primitive roots belonging to n.
Proof: By Lemma 2 result follows:
Theorem 1, Lemma 2 and Corollary 1 combine to show that if an integer n
has a primitive root belonging to it then n must be of the form
n = 2mpk 0 m < 2 and k 0
i.e.n is either pk or 2pk. We now prove that if n is pk or 2pk, p an odd prime then
n has a primitive root belonging to it.
Theorem2: There exist primitive roots belonging to pk and 2pk, p being an odd prime and k 1.
Proof: We first show that there exists a primitive root (mod pk), p odd prime and k 1. We know that If k = 1, there is a primitive root (mod p). Suppose k > 1.
Let a be a primitive root mod p. We shall, starting with a, construct a primitive root mod pk. By definition a has exponent p-1 i.e. ap-1 1 (mod p). If ap-
1 1 (mod p2), then let a1 = a+p. We show a1 is also a primitive root (mod p). Since a1 a (mod p).
(a1)h ah (mod p)
For each integer h.
Hence
(a1)h 1 (mod p) ah 1 (mod p)
a1 is also a primitive root (mod p). Further
For ap-2 1 (mod p2) and (p, p-1) = 1.
Thus we take a primitive root a (mod p) the one for which
ap-1 1 (mod p2).
We next show that.
...... (3)
For k = 2,by choice of a, we are done. Suppose k > 2 and that we have shown
. . . . (4)
We show
Since(a, p) = 1, (a, pk-1 = 1
Therefore by Eulers theorem
. . . (5)
and by (4)(,p) = 1 . . . (6)
Now
. . . (by (5))
1 (mod pk+1) . . . (by
6)
So that a works as a primitive root (mod pk).
Let n be the exponent of a (mod pk).
Then an 1 (mod pk)...7
Also a(pk) 1 (mod pk)kkkkk... (Euler’s Theorem)
n/(pk) pk-1(p-1)
Aspk /an-1.... (by 7)
p /an-1
an 1 (mod p)
But then a has exponent (p) p-1 (mod p) p-1|n.
n = pm (p-1) 0 m k-1
If m < k-1, then m k-2.
But by (3) m > k – 2; thus m=k – 1
n = pk-1 (p-1)
exponent of a is (pk) (mod pk) i.e. a is a primitive root (mod pk).
We now show that 2pk k 1 has primitive roots belonging to it. Let a be a primitive root (mod pk). If a is even, replace a by a1 = a + p so that we can assume that a is an odd primitive root (mod pk). We show a is a primitive root (mod 2pk). Suppose exponent of a (mod 2pk) is m. Then
n | (2pk)( (2pk, a) = 1 and a(2pk) 1 (mod 2pk)
(by Euler’s Theorem)
Now, n |(2pk) = (pk). . . (8)
Also a is a primitive root (mod pk) (pk) is exponent of a (mod pk) and an 1 (mod 2pk)
an 1 (mod pk)
(pk) |n.... (9)
(8) and (9) n = (pk) = (2pk).
a is a primitive root (mod 2pk).
Remark: 1. By the last part of the above theorem, any odd primitive root (mod pk) serves as a primitive root (mod 2pk).
2.The only integers that have primitive roots belonging to them are 2, 4, pk or 2pk, p odd prime and k 1.
Example 1: Let p = 5. We shall find a primitive root mod 52
We know that 2 is a primitive root mod 5.
Since 2 2, 22 4, 23 3, 24 1 (mod 5).
Again 24 1 (mod 52) and 2, 22 4, 25 8, 24 16, 25 7, 2614, 27 3, 28 6, 29 12, 210 24, 211 23, 212 21, 213 17, 214 9, 21518, 216 11, 217 22, 218 19, 219 13, and 220 1 (mod 52), 2 is a primitive root mod 52.
It can be similarly shown that 3 is also a primitive root mod 52.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Indices
Definition: Let a be a primitive root belonging to an integer m.For any integer b coprime to m if b ak (mod m), then k is called index of b modulo m relative to the primitive root a. We write symbolically as
Indab = kif b ak (mod m) or
SimplyInd b = k,whenever it is clear which primitive
root is referred to
Example 2: 3 is a primitive root mod 5. We give indices of 1, 2, 3, 4 (mod 5) relative to 3.
Inter 1234
Index 4312
Or 0
Observe that index of 0 is not defined. Also the concept of index is similar to that of logarithms for real numbers. Indices even obey rules very similar to logarithms.
Theorem3: Let a be a primitive root modulo m and b, c, k any integers, then the following hold:
(i)b c (mod m) Ind b Ind c (mod (m))
(ii)Ind (bc) Ind b + Ind c (mod (m))
(iii)Ind bk k ind b (mod (m))
(iv)Ind 1 0 (mod (m)).
Proof: Let Ind b = r and Ind c = s
Thenb ar (mod m) and c as (mod m)
(i) Ifb c (mod m), then ar as (mod m)
Now,ar as (mod m)
ar-s 1 (mod m)
But by definition of a,
(m) |r-s; consequently
r s (mod (m))
(ii)bc aras (mod m)
bc ar+s (mod m)
Or
But, if t = ind bc then bc at (mod m)
Once again, r + s t (mod (m)) as in (i).
(iii) it is Obvious from the result of (ii)
(iv)Since a is a primitive root modulo m.
The theory of indices is useful only for those modulii which possess primitive roots. Moreover, the table of indices must be prepared for each modulus (which is not so with logarithms). We illustrate this by solving two types of congruences.
Example 3. Solvethe linear congruence
7x 2 (mod 9)
We know 2 is a primitive root modulo 9. Also,
21 2, 22 4, 23 8, 24 7, 25 5 and 26 1 (mod 9). Thus index of 7 is 4 and 2 is 1.
Now 7x 2 (mod 9) is equivalent to
Ind 7 + Ind x Ind 2 (mod (9)
Or4 + Ind x 1 (mod 6)((9) = 6)
OrInd x -3 (mod 6)
3 (mod 6)
Hencex 23 (mod 9)
Orx 8 (mod 9)
Thus solution of 7x 2 (mod 9) are of the form 9t + 8 for t = 0, + 1, + 2, . . . .
Example 4. Solve thecongruence.
11x3 2 (mod 23).
We know 5 is a primitive root modulo 23, Also,
51 5, 52 2, 53 10, 54 4, 55 20, 56 8, 57 17, 58 16, 59 11, 510 9 (mod 23), and
11x3 2 (mod 23) is equivalent to
Ind 11 + 3 Ind x Ind 2 (mod 22)
Or9+3 Ind x 2 (mod 22)
Or3 Ind x -7 (mod 22)
2 Ind x 15 (mod 22)
OrInd x 5 (mod 23)
Hence x 55 (mod 23)
Orx 20 (mod 23)
Thusx = 23t + 20, t = 0; + 1, + 2, . . . . are all solutions of the given congruence.
Summary
In this session we characterized the integers that having primitive roots belonging to them through several lemmas.
Discussed the idea of indices ,also verified that theory of indices is useful only for those modulii which possess primitive root
Assignment
1.Let a be a primitive root modulo pk .Then a is a primitive root modulo p.prove
2.Solve the following congruences
(1) 7x33(mod11)
(2)4x19(mod23)
3.Make a table of indices for the prime 17 with primitive root 5
Quiz
1.Primitive roots of 25 are/is
(a)2(b)3(c)2 and 3(d)none of these
2.Primitive roots of 32 ,33 ,34
(a)0(b)3(c)4(d)none of these
Ans:1 ©2 and 3
2 (d)none of these
Faq
1.Is there exits any primitive roots belonging to 2n
Ans :There are primitive roots belonging to 2n only if n<3.
For every nthereare no primitive roots belonging to 2n
2.Is there any integers that have primitive roots belonging to them
Ans The only integers that have primitive roots belonging to them are 2 ,4 ,pk or 2pk ,p odd prime and k
Glossary
Indices:Let a be a primitive root belonging to an integer m.For any integer b coprime to m if b ak (mod m), then k is called index of b modulo m relative to the primitive root a. We write symbolically as
Indab = kif b ak (mod m) or
SimplyInd b = k,whenever it is clear which primitive
root is referred to