Unit - 3

Order of an integer modulo

3.1 Order of an integer modulo n

You may see strange consequences when you exponentiate an integer number modulo another integer number. 33 = 27 = 12 mod 15, for example, whereas 34 = 81 = 6 mod 15. That is, multiplying 12 by 3 modulo 15 produces a result that is less than 12!? Alternatively, if you multiply 33 by 24 (the amount of hours in a day), you get 33 = 27 = 3 mod 24. Isn't it amusing?

You can even discover a power r such that mr = 1 mod n for some values m > 1. We have 42 = 16 = 1 mod 15 as an example.

The order is defined as the smallest positive integer power r of an integer m modulo a (natural) number n.

mr = 1 mod n.

The order r of m modulo n is shortly denoted by ordn(m). For some constellations, however, there does not exists any positive power. Above we saw, e.g., that 33 = 3 mod 24, i.e., 33 = 31 mod 24, and moreover we directly compute 32 = 34 = 9 mod 24. Hence, any even power of 3 yields 9 modulo 24, and any odd power of 3 is 3 modulo 24.

Worse, there are situations when numbers with a positive power vanish. Take a look at 122 = 144 = 0 mod 24 as an example. There is no positive finite power to provide the order of such numbers, hence the order is specified as infinite.

If n is prime, then any integer that is relatively prime to n has a finite order, according to group theory. For example, if n = 7, the following table can be used to determine the order of any integer m.

The dots (...) represent the fact that anything repeats cyclically. Check it out! More generally, any number m being prime relatively to n has a finite order with respect to n, e.g., for n=15,

The conceivable finite orders modulo n are divisors of the Carmichael function value, and vice versa, any divisor is at least one integer's order. The Carmichael function returns 4 for 15. In fact, in the table above, all divisors of 4 (specifically 1, 2, and 4) may be found as order values! You can use an applet to calculate the order.

Example:

1) The ordering modulo 13 of the positive integers smaller than 13 are shown in the table below:

Solution:

The order of 2 modulo 13 is 12, but the orders of 22 and 23 are 6 and 4, respectively; this is simple to prove.

The integers that likewise have order 12 modulo 13 are powers 2k for which gcd(k, 12) = 1 according to Theorem 8.3.

If an integer has the largest order possible, then we call it a primitive root of .

2) Let us show that if Fn = 22" + 1, n > 1, is a prime, then 2 is not a primitive root of Fn. (Clearly, 2 is a primitive root of 5 = F1.) From the factorization 22n+l - 1 = (22" + 1) (22" - 1), we have

Which implies that the order of 2 modulo Fn does not exceed 2n+I. But if Fn is assumed to be prime, then

And a straightforward induction argument confirms that 22" > 2n+l, whenever n > 1. Thus, the order of 2 modulo Fn is smaller than , we see that 2 cannot be a primitive root of Fn.

3.2 Primitive roots for primes, composite numbers having primitive roots

3.2.1 Primitive roots for primes

A primitive root of a prime  is an integer such that  (mod ) has multiplicative order  (Ribenboim 1996, p. 22). More generally, if  ( and  are relatively prime) and  is of multiplicative order  modulo  where  is the totient function, then  is a primitive root of  (Burton 1989, p. 187). The first definition is a special case of the second since  for  a prime.

A primitive root of a number  (but not necessarily the smallest primitive root for composite ) can be computed in the Wolfram Language using PrimitiveRoot[n].

If has a primitive root, then it has exactly of them (Burton 1989, p. 188), which means that if  is a prime number, then there  are exactly incongruent primitive roots of  (Burton 1989). For , 2, ..., the first few values of are 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554). n has a primitive root if it is of the form 2, 4, , or , where is an odd prime and  (Burton 1989, p. 204). The first few for which primitive roots exist are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ... (OEIS A033948), so the number of primitive root of order  for , 2, ... Are 0, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144).

The smallest primitive roots for the first few primes  are 1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, ... (OEIS A001918). Here is table of the primitive roots for the first few n for which a primitive root exists (OEIS A046147).

2	1
3	2
4	3
5	2, 3
6	5
7	3, 5
9	2, 5
10	3, 7
11	2, 6, 7, 8
13	2, 6, 7, 11

The largest primitive roots for , 2, ..., are 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, ... (OEIS A046146). The smallest primitive roots for the first few integers n are given in the following table (OEIS A046145), which omits when does not exist.

Let  be any odd prime , and let

 (1)

Then

 (2)

(Ribenboim 1996, pp. 22-23). For numbers m with primitive roots, all y satisfying  are representable as

 (3)

Where  , 1, ..., , t is known as the index, and y is an integer. Kearnes (1984) showed that for any positive integer m, there exist infinitely many primes p such that

 (4)

Call the least primitive root . Burgess (1962) proved that

 (5)

For  and  positive constants and  sufficiently large

3.2.2 Composite numbers having primitive roots

We now know when a prime number has a primitive root (it always does) and how many there are ((p 1)). What about the concept of composite numbers?

Let's start with the most basic type of composite number: prime powers.

6.33 is a lemma. Allow p to be an odd prime with r as the primitive root. Then either r or r + p modulo p 2 is a primitive root.

6.34 remark Since p + r is a primitive root modulo p, this suggests that there is some number that is a primitive root modulo p and also modulo p 2.

Proof. We know that ordp r = φ(p) = p − 1. Let n = ordp 2 r. By definition r n ≡ 1 mod p 2 , and thus r n ≡ 1 mod p. This implies that p − 1 = ordp r|n.

But we know that ordp 2 r|φ(p 2 ) = p(p − 1), so we have p − 1|n|p(p − 1). Thus either n = p − 1 or n = p(p − 1). If n = p(p − 1) then r is a primitive root modulo p 2 ; so suppose n = p − 1.

Let s = r + p. Then since s is also a primitive root modulo p, by the same logic we know that ordp 2 s is either p − 1 or p(p − 1). We wish to show that ordp 2 s 6= p − 1.

By the binomial theorem, we compute

s p−1 = (r + p) p−1 = X p−1 i=0  p − 1 i  p i r p−1−i

= r p−1 + (p − 1)prp−2 + · · · + (p − 1)p p−2 r + p p−1

≡ r p−1 + (p − 1)prp−2 mod p 2

≡ 1 + (p − 1)prp−2 mod p 2 .

But since p6 |r we see that (p − 1)prp−2 6≡ 0 mod p 2 so s p−1 6≡ 1 mod p 2 as desired.

Thus ordp 2 s 6= p − 1, and the only remaining possibility is that ordp 2 s = p(p − 1) = φ(p 2 ).

Lemma 6.37. Let p be an odd prime. Then p k has a primitive root for any k ∈ N. Moreover, if r is a primitive root modulo p 2 , then r is a primitive root modulo p k for any k ∈ N.

Proof. By lemma 6.33 we know that p has a primitive root r that is also a primitive root modulo p 2 , and thus r p−1 6≡ 1 mod p 2 .

First we will prove by induction that r p k−2 (p−1) 6≡ 1 mod p k for any k ≥ 2. The base case when k = 2 follows from Lemma 6.33. Suppose the assertion is true for k, and we will prove it for k + 1.

By inductive hypothesis, we know that

r p k−2 (p−1) 6≡ 1 mod p k.

But also (r, p) = 1 since r is a primitive root, and thus (r, pk−1) = 1. Thus φ(p k−1 ) = p k−2 (p − 1)

And thus r p k−2 (p−1) = r φ(p k−1 ) ≡ 1 mod p k−1 .

Thus we can find some integer such that

r p k−2 (p−1) = 1 + dpk−1

Because the congruence would hold moduldo p k otherwise, p6 |d is used. Both sides of this can be raised to the pth power, which produces

r p k−2 (p−1)(p) = X p i=0  p i (dp) (k−1)i

r p k−1 (p−1) = 1 + dpk + p k+1 (stuff)

r p k−1 (p−1) ≡ 1 + dpk mod p k+1

≡ 1 mod p k+1

Since p6 |d. Thus by induction, for any k ≥ 2 we have

r p k−1 (p−1) 6≡ 1 mod p k+1.

Now we wish to show that r is a primitive root modulo p k. Let n = ordp k r. We know that n|φ(p k ) = p k−1 (p − 1). Further, we know that ordp r = p − 1 so we must have p − 1|n. So n = p t (p − 1) for some 0 ≤ t ≤ k − 1.

But we know that

r p k−2 (p−1) 6≡ 1 mod p k,

So we must have t < k − 2. Thus t = k − 1 and so ordr = p k−1 (p − 1) = φ(p k ), and r is a primitive root modulo p k .

3.3 Euler's criterion

The congruence a(p1)/2(ap)(modp) holds if an integer an is not divisible by a prime number p>2, where (ap) is the Legendre symbol. Thus, the Euler criterion specifies that a number a0(modp) must be a quadratic residue or non-residue modulo p. .

Euler also came up with a more general conclusion: If and only if, a number a0(modp) is a power residue of degree n modulo a prime number p.

a(p−1)/δ≡1(modp)

Where δ=hcf(p−1,n)

Both these assertions carry over easily to the case of a finite field.

Theorem 1 (Euler’s Criterion).

Let  be an odd prime. Let  be an integer that is relatively prime to . Then the integer  is a quadratic residue modulo  if and only if . On the other hand, the integer  is a quadratic nonresidue modulo p if and only if .

The task of determining the status of quadratic residue, according to Euler's Criterion, is as simple as completing a modular exponentiation. This can be done with modular arithmetic software or a calculator. The rapid powering approach can also be used to programme the exponentiation if desired.

Though Euler's Criterion (together with a calculator for modular arithmetic) is a foolproof method of determining the status of quadratic residues, the rule of quadratic reciprocity can make the process even easier. As the examples below indicate, applying the rule of reciprocity to check the status of quadratic residues may not need any modular exponentiation at all, and if it is, it is of a significantly lower scale.

Euler's Criterion also provides us with a number of fundamental truths concerning quadratic residues.

Theorem 2

Let  be an odd prime. The following properties are true:

• If  and  are both residues modulo , then the product is a residue modulo .
• If If  and  are both nonresidues modulo , then the product  is a residue modulo .
• If  and are such that one of them is a residue modulo  and the other is a nonresidue modulo , then the product  is a nonresidue modulo .

Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime . The product of two integers of different types is always a nonresidue modulo the odd prime . The theorem follows from Euler’s criterion and from the fact that .

In arithmetic modulo a prime p, there exists a primitive root modulo  and that any primitive root generates by powering all the integers that are relatively prime to the modulus . Let  be a primitive root modulo an odd prime . It then follows that the quadratic residues modulo  are the even powers of  and the nonresidues are the odd powers of . A related fact is that when  is an odd prime and when  and  are relatively prime, the equation  either has two solutions or has no solutions.

Theorem 3

Let  be a primitive root modulo an odd prime . For any  that is relatively prime to  , the following is true:

•  is a quadratic residue modulo  if and only if  is of the form  for some positive integer ,
•  is a quadratic nonresidue modulo  if and only if  is of the form  for some positive integer .

Examples:

1) Take  as an example. To determine whether this equation is solvable, we can check each integer in the interval . Euler's Criterion reduces the solvability question to a modular exponential problem. It can be shown that . Thus  has solutions.

On the other hand, the equation   has no solutions since 

2) Determine if 2, 3, or 5 are primitive roots of 5639 using Euler's Criterion for quadratic residues and Legendre symbols.

Solution:

The potential orders of 5369 are divisors of 5368, to begin with. 5368 has the divisors 1, 2, 2819, and 5638. The ordering of 2, 3, 5, and 7 will not be 1, 2, or 3. As a result, we can see if the orders 2, 3, 5, or 7 are 2819.

Now we know that from Euler's Criterion that . Given that, we can evaluate the Legendre symbols (2/5369),(3/5369),(5/5369),(7/5369).

Since 53691, the Legendre symbol (2/5369)=1 (mod8). Because 2 has order 2819, it is not a primitive root of 5369.

(3/5369)=(5369/3)=(2/3)=1 is the Legendre symbol. Because 3 has order 2819, it is a primitive root of 5369.

(5/5369)=(5369/5)=(4/5)=1 is the Legendre symbol. Because 5 has order 2819, it is not a primitive root of 5369.

3.4 The Legendre symbol, Jacobi symbol and their properties

3.4.1 Jacobi Symbol

The Legendre symbol is where the bottom argument is always an odd prime and the top argument can be any integer. When  is an integer that is relatively prime to the odd prime , the Legendre symbol  carries information on whether the integer  is quadratic residue modulo p. The following gives the definition of the Legendre symbol.

The Jacobi symbol  has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer  has the prime factorization , the Jacobi symbol is defined as follows:

For convenience, we define . A slightly different, but equivalent, definition is that whenever the odd integer  has the prime factorization  (the prime numbers  are not necessarily distinct), the symbol  is defined as follows:

According to the prime factorization of the bottom argument, the Jacobi symbol is defined using the Legendre symbol.

Properties of Jacobi Symbol

There are two natural questions now that the Jacobi symbol has been defined based on the Legendre symbol.

Does the value of  indicates that  is a quadratic residue or nonresidue modulo ?

The Legendre symbol is a flexible tool because it follows a set of principles (for example, the law of quadratic reciprocity). Is the Jacobi sign compliant with these guidelines? In theory, evaluating the Jacobi symbol entails factoring the sign's bottom argument. This appears to be a limitation at first glance. However, if the Jacobi symbol follows the Legendre symbol's laws, including the law of quadratic reciprocity, evaluating the Jacobi symbol will be equally as simple.

For the first question, the following is true: If  is a quadratic residue modulo , then . The contrapositive of this statement is that if , then the number  is a quadratic nonresidue modulo the odd integer , i.e. the equation has no solutions. However, the value of  does not imply that  is a quadratic residue modulo . For example,  but the equation  has no solutions. Note that both equations  and  have no solutions. This means that the value of  is the product of two Legendre symbols of -1.

3.4.2 Legendre symbol:

In number theory, the Legendre symbol is a quadratic character modulo an odd prime number p with values 1, 1, 0: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is 1. At zero, it has no value.

Adrien-Marie Legendre introduced the Legendre symbol in 1798[1] as part of his attempts to prove the law of quadratic reciprocity. The Jacobi symbol and higher-order Dirichlet characters are examples of generalisations of the symbol. The Legendre symbol inspired the invention of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol, due to its notational convenience.

Properties of the Legendre symbol

The Legendre symbol has a number of helpful qualities that, when combined with the law of quadratic reciprocity, can be utilised to efficiently compute it.

• The Legendre symbol reveals the parity of a non-zero integer mod p. That is, given a generator {\displaystyle g\in \mathbb {F} _{p}^{*}} , the {\displaystyle x=g^{r}}n {\displaystyle x}X is a quadratic residue if and only if {\displaystyle r}r is even. This also shows that half of the non-zero elements in {\displaystyle \mathbb {F} _{p}^{*}} are quadratic residues.
• If {\displaystyle p\equiv 3{\text{ mod }}4}  then the fact than

gives us that {\displaystyle a=x^{(p+1)/4}}  is the square root of the quadratic residue {\displaystyle x}x.

The Legendre symbol is periodic in its first (or top) argument: if a ≡ b (mod p), then

{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}

• The Legendre symbol is a completely multiplicative function of its top argument:

{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).} {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}

A residue is formed by the product of two numbers that are both quadratic residues or quadratic non-residues modulo p, whereas a non-residue is formed by the product of a residue and a non-residue. The Legendre sign of a square is an exception:

{\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}}

• When viewed as a function of a, the Legendre symbol {\displaystyle \left({\frac {a}{p}}\right)}(a/p) is the unique quadratic (or order 2) Dirichlet character modulo p.
• The first supplement to the law of quadratic reciprocity:

{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ if }}p\equiv 3{\pmod {4}}.\end{cases}}}

• The second supplement to the law of quadratic reciprocity:

{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1&{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}.\end{cases}}}

• Special formulas for the Legendre symbol {\displaystyle \left({\frac {a}{p}}\right)}(a/p)  for small values of a:
  • For an odd prime p ≠ 3,

{\displaystyle \left({\frac {3}{p}}\right)=(-1)^{{\big \lfloor }{\frac {p+1}{6}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1&{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}.\end{cases}}}

• For an odd prime p ≠ 5,

• {\displaystyle \left({\frac {5}{p}}\right)=(-1)^{{\big \lfloor }{\frac {2p+2}{5}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1&{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}.\end{cases}}}
• The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … are defined by the recurrence F1 = F2 = 1, Fn+1 = Fn + Fn−1. If p is a prime number then

{\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}For example,

{\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}

{\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}

{\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}

{\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}

Example:

Thus we know that 12345 is a quadratic residue modulo the prime 13337. Indeed: 

For example, in a more generic sense, one gets:

.

,

.

2) Calculate the Legendre symbol (1000/11).

Solution:

We know that 11 is an odd prime, and 11∤1000, so the Legendre symbol (1000/11) is defined. Let's start with a breakdown of 1000's prime power decomposition. That is, 1000=23⋅53. Hence it follows that by (D) that:

By (C), we know that , and , hence:

By (I), we know that since 11≡3(mod8):

5≡1(mod4), and 11≡3(mod4). By (G), we know that hence:

By (B), we can reduce 11. That is 11≡1(mod5), so:

And by (C), 1 is a square, so Hence

Hence the Legendre symbol (1000/11)=−1. Hence the quadratic congruence x2≡1000(mod11) has no solutions since 1000 is a quadratic nonresidue (mod 11).

3) Does the quadratic congruence x2≡341(mod17) have solutions?

Solution:

By evaluating the Legendre symbol (341/17), we can see if this quadratic congruence has solutions. We know this Legendre symbol is described by (A) because 17 is an odd prime and 17341 is a prime number. We'll start by reducing 341, then utilise (B) to evaluate this Legendre symbol. It's worth noting that we could have used this in Example 1 as well! 341≡1(mod17). As a result, it follows that:

And since 1 is a square, then Hence it follows that the Legendre symbol (341/17)=1. So the quadratic congruence x2≡341(mod17) has solutions. In fact, we can find them rather easily:

As a result, x is either 1 (mod 17) or -1. (mod 17). Because -1 isn't in least residue, we'll use 16 instead (mod 17). As a result, our answers are x = 1 and x = 16.

4) Evaluate the Legendre symbol (14014/5).

We know that this Legendre symbol is defined since 5 is an odd prime and 5∤14014. Using property (B), we know that 14014≡4(mod5). Hence:

We know that 4 is a square since  Hence (14014/5)=1.

5) Evaluate the Legendre symbol (342/113).

Solution:

This Legendre symbol is specified once more. 3423, according to property (B) (mod113). Hence:

It's worth noting that 3(mod4) and 3(mod1) (mod4). As a result of (G):

We get 1132(mod3) by lowering 113 (mod 3), so:

Notice that 3≡3(mod8), so by (I), and hence the Legendre symbol (342/113)=−1.

3.5 Quadratic reciprocity

The Legendre symbol is considerably aided by the law of quadratic reciprocity, which was discovered by Euler and Legendre and verified by Gauss.

We'll start with the following theorem:

Theorem: Let p be an odd prime and q be some integer coprime to p. Let m=⌊q/p⌋+⌊2q/p⌋+...+⌊((p−1)/2)q/p⌋.

Then m=u+(q−1)(mod2), where as in Gauss' Lemma, u is the number of elements of {q,2q,...,q(p−1)/2} which have a residue greater than p/2. In particular when q is odd, m=u(mod2).

Proof: For each i=1,...,(p−1)/2, the equation iq=p⌊iq/p⌋+ri holds for some 0<ri<p. Reading the proof of Gauss' Lemma, we see these are precisely the bi and ci.

Then summing these equations modulo 2 gives

q(p2−1)/8=pm+b1+...+bt+c1+...+cu=pm+b1+...+bt+up+(p−c1)+...+(p−cu)=pm+up+1+2+...+(p−1)/2=pm+up+(p2−1)/8

Since p is odd, we have m=u+q−1(mod2).

Theorem (Law of Quadratic Reciprocity): Let p,q be distinct odd primes. If p=q=−1(mod4), then

(pq)=−(qp)

Otherwise

(pq)=(qp).

Which we can state as

(pq)(qp)=(−1)p−12q−12

Proof: From above, we need only show

m+n=(p−1)(q−1)/4

Where m=⌊q/p⌋+⌊2q/p⌋+...+⌊((p−1)/2)q/p⌋, and n is similarly defined by swapping p and q.

Eisenstein discovered a beautiful geometrical proof. Consider the line L from (0,0) to (p,q), as well as the rectangle R with (0,0) and (p/2,q/2) corners. How many lattice points are completely included within R?

When you calculate the area of a rectangle, you get (p1)(q1)/4. Alternatively, because no lattice points may lie on L in R because p,q are coprime, we can count the number of points above and below L inside R.

Consider the points on the x=1 line below L. 1,2,...,q/p are their y-coordinates. There are 2q/p points for x=2, and so on, for a total of m points below the L. Similarly, in R, there are n points above L, proving the conclusion.

We can restate the proof algebraically. Consider thenumbers py−qx for x=1,...,(p−1)/2 and y=1,...,(q−1)/2. There are a total of (p−1)(q−1)/4 numbers, This is not always the case. Because p and q are coprime, none of them are zero. After noticing that n of them are positive and m are negative, the result follows.

Example:

(31103)=−(10331)=−(1031)=−(231)(531)=−(−1)(531)

Since 2=−5(mod8). Next,

(531)=−(315)=−(15)=−1.

Hence 31 is a quadratic nonresidue modulo 103.

We could assume we should stick to our initial modular exponentiation for computing the Legendre symbol because this method is faulty because it relies on factoring. But it turns out that if we extend the Legendre sign, everything is OK.

Key takeaways:

The law of quadratic reciprocity is a key fact of number theory; it allows us to determine if a congruence x2 a (mod p) is solvable even if it does not lead to a specific solution.

3.6 Quadratic congruences with composite moduli

3.6.1 Quadratic congruences

An integer q is called a quadratic residue modulo n in number theory if it is congruent to a perfect square modulo n; that is, if there exists an integer x such that:

If q is not a quadratic nonresidue modulo n, it is called a quadratic nonresidue modulo n.

Quadratic residues, originally an abstract mathematical term from the branch of number theory known as modular arithmetic, are today used in applications ranging from acoustical engineering to encryption and huge number factoring.

3.6.2 Composite moduli

If the modulus n has been factored into prime powers the solution was discussed above.

If n is not congruent to 2 modulo 4 and the Kronecker symbol {\displaystyle \left({\tfrac {a}{n}}\right)=-1}  then there is no solution; if n is congruent to 2 modulo 4 and {\displaystyle \left({\tfrac {a}{n/2}}\right)=-1} , then there is also no solution. If n is not congruent to 2 modulo 4 and {\displaystyle \left({\tfrac {a}{n}}\right)=1}, or n is congruent to 2 modulo 4 and {\displaystyle \left({\tfrac {a}{n/2}}\right)=1}, there may or may not be one.

If the complete factorization of n is not known, and {\displaystyle \left({\tfrac {a}{n}}\right)=1}  and n is not congruent to 2 modulo 4, or n is congruent to 2 modulo 4 and {\displaystyle \left({\tfrac {a}{n/2}}\right)=1} , the problem is known to be equivalent to integer factorization of n (i.e. an efficient solution to either problem could be used to solve the other efficiently).

The above discussion indicates how knowing the factors of n allows us to find the roots efficiently. Say there were an efficient algorithm for finding square roots modulo a composite number. The article congruence of squares discusses how finding two numbers x and y where x2 ≡ y2 (mod n) and x ≠ ±y suffices to factorize n efficiently. Create a random integer, square it modulo n, and use the square root procedure to get the root. Repeat until it gives a number that is not identical to the one we squared (or its negative modulo n), then use the congruence of squares procedure. The efficiency of the factoring algorithm is determined by the root-exact finder's properties.S

Computing the Legendre symbol quickly determines whether an is a quadratic residue or a nonresidue modulo n (denoted a R n or a N n) for prime n. For composite n, however, this results in the quadratic residuosity problem, which is not known to be as difficult as factorization but is thought to be difficult.

However, if we want to know if there is a solution for x less than a specific limit c, this problem is NP-complete; however, it is a fixed-parameter tractable problem, where c is the parameter.

In general, the following theorem can be used to determine if an is a quadratic residue modulo composite n:[37]

Let n > 1, and gcd(a,n) = 1. Then x2 ≡ a (mod n) is solvable if and only if:

• The Legendre symbol {\displaystyle \left({\tfrac {a}{p}}\right)=1}  for all odd prime divisors p of n.
• a ≡ 1 (mod 4) if n is divisible by 4 but not 8; or a ≡ 1 (mod 8) if n is divisible by 8.

Note: This theorem essentially requires that the factorization of n is known. Also notice that if gcd(a , n)= m, then the congruence can be reduced to a/m ≡ x2/m (mod n/m), but then this takes the problem away from quadratic residues (unless m is a square).

Numerical:

1) Let  be a prime number. Prove that there exists x∈Z for which p ∣ x2−x+3 if and only if there exists y∈Z for which p ∣ y2−y+25.

Solution:

The statement is trivial for p≤3, so we can assume that p≥5.

Since p ∣ x2−x+3 is equivalent to p ∣ 4(x2−x+3)=(2x−1)2+11, integer x exists if and only if −11 is a quadratic residue modulo p. Likewise, since 4(y2−y+25)=(2y−1)2+99, y exists if and only if −99 is a quadratic residue modulo p. Now the statement of the problem follows from

2) Solve  .

According to Euler’s Criterion, the equation  has solutions since . To find the solutions, we keep adding the modulus to  until we get a perfect square.

So we have  , which gives and . The solutions are  and .
 

3) Solve .

Since , the equation has solutions. We then add the modulus repeatedly to 899 until we get a perfect square (with the aid of an Excel spreadsheet)

So we have , which gives  and . The solutions are   and .
 

4) Solve  

Since , the equation has no solutions according to Euler’s Criterion.

Q. The two-digit integers form 19 to 92 are written consecutively to form the large integer N = 192021 · · · 909192. Suppose that 3k is the highest power of 3 that is a factor of N. What is k?

Solution:

We know that N ≡ S(N) mod 9. S(N) = 1+9+9+0+9+1+9+2+10(2+...+8)+7(0+...9) =

40 + 10(35) + 7(45) = 40 + 350 + 315 = 705. Then N ≡ S(N) ≡ S(S(N)) ≡ S(705) ≡ 12 ≡ 3

Mod 9. Thus, it is only divisible by 3 and not 9, and k = 1.

Q. In year N, the 300th day of the year is a Tuesday. In year N + 1, the 200th day is also a Tuesday. On what day of the week did the 100th day of the year N − 1 occur?

Solution

There are either 65 + 200 = 265 or 66 + 200 = 266 days between the first two dates depending upon whether or not year N is a leap year. Since 7 divides into 266, then it is possible for both dates to Tuesday; hence year N + 1 is a leap year and N − 1 is not a leap year. There are 265 + 300 = 565 days between the date in years N, N − 1, which leaves a remainder of 5 upon division by 7. Since we are subtracting days, we count 5 days before Tuesday, which gives us Thursday.

Q. Mrs. Walter gave an exam in a mathematics class of five students. She entered the scores in random order into a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) were 71,76,80,82,and 91. What was the last score Mrs. Walter entered.

Solution:

The sum of the first three numbers is divisible by 3. The sum of the first four numbers is divisible by 4. If we write out all 5 numbers in mod 3, we get 2, 1, 2, 1, 1, respectively. Clearly 1 the only way to get a number divisible by 3 by adding three of these is 1 + 1 + 1, so those scores must be entered first. Now we have an odd sum, so we must add 71 in order for the sum to be divisible by 4. That leaves 80 for the last score entered.

Q. Find the number of integers n, 1 ≤ n ≤ 25 such that n 2 + 3n + 2 is divisible by 6.

Solution

(n + 1)(n + 2) ≡ 0 ≡ 2 ∗ 3 ≡ 5 ∗ 6 ≡ 6 ∗ 1 mod 6. Therefore (n + 1) ≡ 2, 5, 6 mod 6, and n ≡ 1, 4, 5 mod 6. There are 5 + 4 + 4 = 13 of these numbers between 1 and 25.

Q. If n! denotes the product of the integers 1 through n, what is the remainder when (1! + 2! + 3! + 4! + 5! + 6! + ...) is divided by 9?

Solution:

First of all, we know that k! ≡ 0 (mod 9) for all k ≥ 6. Thus, we only need to find

(1! + 2! + 3! + 4! + 5!) (mod 9).

1! ≡ 1 (mod 9)

2! ≡ 2 (mod 9)

3! ≡ 6 (mod 9)

4! ≡ 24 ≡ 6 (mod 9)

5! ≡ 5 · 6 ≡ 30 ≡ 3 (mod 9)

Thus,

(1! + 2! + 3! + 4! + 5!) ≡ 1 + 2 + 6 + 6 + 3 ≡ 18 ≡ 0 (mod 9)

So the remainder is 0.

Q. Prove that 2n + 6 · 9 n is always divisible by 7 for any positive integer n.

Solution

2 ≡ 9 (mod 7) =⇒ 2 n ≡ 9

n (mod 7) =⇒ 2 n + 6 · 9

n ≡ 7 · 9

n ≡ 0 · 9

n ≡ 0 (mod 7).

Q. The positive integers N and N2 both end in the same sequence of four digits abcd when written in base 10, where digit a is nonzero. Find the three-digit number abc.

Solution

We have that N2 − N = N(N − 1) ≡ 0 mod 10000. Thus, N(N − 1) must be divisible by both 54 and 24. Note, however, that if either N or N − 1 has both a 5 and a 2 in its factorization, the other must end in either 1 and 9, which is impossible for a number that is divisible by either 2 or 5. Thus, one of them is divisible by 24 = 16, and the other is divisible by 54 = 625. Noting that 625 ≡ 1 mod 16, we see that 625 would work for N, except the thousands digit is 0. The other possibility is that N is a multiple of 16 and N − 1 is a multiple of 625. In order for this to happen, N − 1 must be congruent to −1 mod 16. Since 625 ≡ 1 mod 16, we know that 15 ∗ 625 = 9375 ≡ 15 ≡ −1 mod 16. Thus, N − 1 = 9375, so N = 9376, and our answer is 937.

Q. When 30! is computed, it ends in 7 zeros. Find the digit that immediately precedes these zeros.

Solution

30!/107 = 226 ∗ 314 ∗ 57 ∗ 74 ∗ 112 ∗ 132 ∗ 171 ∗ 191 ∗ 231 ∗ 291/107 = 219 ∗ 314 ∗74 ∗ 112 ∗ 132 ∗171 ∗ 191 ∗ 231 ∗ 291.

So, 30! = 219 ∗ 314 ∗ 74 ∗ 112 ∗ 132 ∗ 171 ∗ 191 ∗ 231 ∗ 291 ≡ 8 ∗ 9 ∗ 1 ∗ 1 ∗ 9 ∗ 7 ∗ 9∗ 3 ∗ 9 ≡ (−2) ∗ (−1) ∗ (−1) ∗ (−3) ∗ (−1) ∗ 3 ∗ (−1) ≡ 18

≡ 8

Q. For how many positive integral values of x ≤ 100 is 3x – x 2 divisible by 5?

Solution

Note that 34 ≡ 81 ≡ 1 mod 5. Let x be defined as x ≡ s mod 20, where s ≤ 20. Then

x ≡ s mod 4 and x ≡ s mod 5. These imply that 3x ≡ 3

s mod 20 and x

2 ≡ s 2 mod 20, so 3 x − x

2 ≡ 3

s − s

2 ≡ 0 mod 20.

After trying values, you will find that s = 2, 4, 16, or 18 are the only values possible. Thus, that are 4 ∗ 5 = 20 possible values of x ≤ 100.

Q. Let S be the set of integers between 1 and 240 that contain two 1’s when written in base 2. What is the probability that a random integer from S is divisible by 9?

Solution

Note that since 26 = 64 ≡ 1 (mod 9), the powers of 2 form a cyclic of length 6 in (mod 9).

Moreover, for any non-negative integer n, 26n ≡ 1 (mod 9), 26n+1 ≡ 2 (mod 9), 26n+2 ≡ 4 (mod 9)26n+3 ≡ 8 ≡ −1 (mod 9), 26n+4 ≡ 16 ≡ −2 (mod 9), 26n+5 ≡ 32 ≡ −4 (mod 9)

The solutions that work are in the form 2a + 2b because they must have exactly two 1’s in

Their binary representation. Pairs of a and b have to be such that 2a and 2b add up to 0 (mod 9). Thus, (a, b) must be in one of the following forms:

(6c, 6d + 3), (6c + 1, 6d + 4), or (6c + 2, 6d + 5)

Since the solutions are between 1 and 240, there are 7 · 7 = 49 choices for the first pair,

7 · 6 = 42 choices for the second pair, and 7 · 6 = 42 choices for the third pair. Thus, there are

49 + 42 + 42 = 133 possible solutions in total. Since there are 402 = 780 numbers that have exactly two 1’s in their binary representation to choose from, the probability that one of them is divisible by 9 is 133780.

Q. Prove that if a ≡ b (mod n), then for all positives integers e that divide both a and b,ae ≡be(mod ngcd(n, e))

Solution

[Proof:]

Let a = ce and b = de for some c, d ∈ Z. Then,

a ≡ b (mod n) =⇒ (a − b) = mn

=⇒ (ce − de) = mn

=⇒ (c − d)(e) + (−m)(n) = 0

=⇒ (c − d)( egcd(n, e)) + (−m)( ngcd(n, e))

= 03

Since egcd(n, e) and n gcd(n, e) are relatively prime, their coefficients must me multiples of the other one, so (c − d) is a multiple of n gcd(n, e)

=⇒ (c − d) ≡ 0 (mod n gcd(n, e))

=⇒ c ≡ d (mod ngcd(n, e))

=⇒ae ≡be(mod ngcd(n, e))

Q. Calculate the Legendre symbol (1000/11).

Solution

We know that 11 is an odd prime, and 11∤1000, so the Legendre symbol (1000/11) is defined. First, let's break 1000 down into its prime power decomposition. That is, 1000=23⋅53. Hence it follows that by (D) that:

(100011)=(2311)(3311)=(2211)(211)(5211)(511)

By (C), we know that (2211)=1, and (5211)=1, hence:

(100011)=(211)(511)

By (I), we know that (211)=−1 since 11≡3(mod8):

(100011)=(−1)(511)

5≡1(mod4), and 11≡3(mod4). By (G), we know that (511)=(115), hence:

(100011)=(−1)(115)

By (B), we can reduce 11. That is 11≡1(mod5), so:

(100011)=(−1)(15)

And by (C), 1 is a square, so (15)=1, hence:

(100011)=(−1)(1)(100011)=−1

Hence the Legendre symbol (1000/11)=−1. Hence the quadratic congruence x2≡1000(mod11) has no solutions since 1000 is a quadratic nonresidue (mod 11).

Q. Does the quadratic congruence x2≡341(mod17) have solutions?

Solution

We can determine if this quadratic congruence has solutions by evaluating the Legendre symbol (341/17). By (A), we know this Legendre symbol is defined since 17 is an odd prime and 17∤341. For evaluating this Legendre symbol, we are going to first use (B) to reduce 341. Note that we could have used this in example 1 too! 341≡1(mod17). Hence it follows that:

(3417)=(17)

And since 1 is a square, then (17)=1. Hence it follows that the Legendre symbol (341/17)=1. So the quadratic congruence x2≡341(mod17) has solutions. In fact, we can find them rather easily:

x2≡341(mod17)x2≡1(mod17)

So x is 1 (mod 17) or -1 (mod 17). -1 is not in least residue, so instead our other solution is 16 (mod 17). Hence our solutions are x = 1 and x = 16.

Q. Evaluate the Legendre symbol (14014/5).

Solution

We know that this Legendre symbol is defined since 5 is an odd prime and 5∤14014. Using property (B), we know that 14014≡4(mod5). Hence:

(140145)=(45)

We know that 4 is a square since (45)=(225). Hence (14014/5)=1.

Q. Evaluate the Legendre symbol (342/113).

Solution

Once again, this Legendre symbol is defined. By property (B), 342≡3(mod113). Hence:

(342113)=(3113)

Notice that 3≡3(mod4) and 3≡1(mod4). Hence by (G):

(3113)=(1133)

And reducing 113 (mod 3), we obtain 113≡2(mod3), so:

(1133)=(23)

Notice that 3≡3(mod8), so by (I),(23)=−1, and hence the Legendre symbol (342/113)=−1.

Q. Suppose that g and h are primitive roots of p. Is it possible that gh is a primitive root of p?

Solution

We first note that if g and h are primitive roots of p, then (g/p)=−1, and (h/p)=−1 since primitive roots of quadratic non-residues. By property (D), it thus follows that (gh/p)=(g/p)(h/p)=(−1)(−1)=1. Hence gh is NOT a primitive root of p. Hence if g and h are primitive roots of p, then gh is NOT a primitive root of p.

Q. Suppose that 2 and 3 are primitive roots of p. Is it possible that 6 is a primitive root of p?

Solution

We note that this question is almost identical to example 5. First, we note that if 2 is a primitive root of p, then it follows that (2/p)=−1 and (3/p)=−1. Hence (6/p)=(2/p)(3/p)=(−1)(−1)=1, so 6 is NOT a primitive root of p.

Q. Evaluate  where  12408107 and  4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

Solution

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol  is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that  is a quadratic nonresidue modulo the odd integer , i.e. the equation  has no solutions. 

Q. Evaluate  where n= 48746413 and a=17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

Solution

The result of  =1gives ambiguous information about the status of  a=17327467 being a quadratic residue or nonresidue modulo  n=48746413. In this case, the Jacobi symbol cannot tell us whether the equation  has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that a=3049 x 5683 and n=7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

By knowing the factoring of n, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations:  and. The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation  has no solutions. Hence a=17327467 is a quadratic nonresidue modulo n-48746413=7109 x 6857. 

References:

1. Thomas Koshy, Elementary Number Theory with Applications (2nd Edition), Academic Press, 2007.

2. Neville Robinns, Beginning Number Theory (2ndEdition), Narosa Publishing House Pvt. Limited, Delhi,2007.