Linear and Quadratic Equations Modulo Primes

DRAFT

In this lecture we discuss solving linear and quadratic equations modulo prime p. To start, we
examine the simple linear case. In the quadratic case the problem is either trivial or can be reduced
to finding square roots in Z_p. From there we see that the square root can be found in P or NP
depending on p. Finally, we describe a general algorithm for solving quadratic equations mod p.

1 Linear Diophantine Equations

First, we study linear equations mod p.

Definition 1. A linear equation is an equation in the following form ax + by = c.

Theorem 1. s.t. ax + ny = b ax ≡ b (mod n)

Proof. A solution exists only if d = GCD(a, n)|b. If so, replace the equation by
. Thus, in

Example: 10x ≡ 6 (mod 12), GCD(10, 12) = 2. Then -x ≡ 5x ≡ 3 (mod 6), so x ≡ -3 ≡ 3
(mod 6). The solutions mod 12 are x = 3 and x = 9.

2 Quadratic Equations

In this section we solve quadratic equations of the form ax² + bx + c = 0 mod p. We will assume
a=1 because we can always multiply the equation by a^-1 ∈ Z_p to put the equation in the form
x² + bx + c = 0. We consider the cases where p = 2 and p > 2 seperately.

2.1 Case p = 2

When p=2 there are only 4 possibilities for the equation so we simply list the solutions:

2.2 Case p = odd prime

In this section we show that solving quadratic equations mod p can be reduced to the problem of
finding square roots in Z_p.
Theorem 2. The quadratic equation x² + bx + c = 0 is solvable in .

Proof. First, we derive the quadratic equation in Z_p where a = 1:

Then the theorem follows from the definition of the Legendre symbol:

	# of solutions

Note that when b² - 4c ≡ 0 (mod p) then .

2.3 Finding square roots in Z_p

Key Idea: To find , express x = y^e, e even. Then . We break this into additional
cases by considering p ∈ Z₄.

2.3.1 Case p ≡ 3 mod 4

In this section we use the fact that . Since p is an odd prime . Thus
. Similarly, . Since p ≡ 3 (mod 4), s.t. p = 4k + 3. Then
is also odd.

Theorem 3. In a finite abelian group G of odd order order, squaring is onto.

Proof. Let = x² and show that given x ∈ G we can find y ∈ G s.t. = x. Let x ∈ G and
|G| = m = 2k + 1. Then  . So and = x.

Theorem 4. In , if p ≡ 3 (mod 4) then .

Proof. Recall that and s.t. p = 4k +3. Then . By
the previous theorem so .

2.3.2 Case p ≡ 1 mod 4

To find in we will pick a t such that f(y) = y² + ty + a is irreducible over Z_p[y]. Fact: f(y)
is irreducibly over . We will show that ≈ 50% of t’s will work so we can
pick t uniformly random. We will work in the finite field F = Z_p[y]/f(y) with p² elements.

Definition 2. F has an automorphism given by = x^p called the Frobenius automorphism.

Theorem 5. In F,

Proof. The roots of y² + ty + a = 0 are y, y^p. Thus y^p+1 = a (in F) because p + 1 is even. Thus, if
, we have .

Example: Find in Z₅. Let a = 4. Then t² - 4a = t² - 16 = t² - 1

Choices for t

Choose t = 2 for example. Then F = Z₅[y]/(y² + 2y + 4). Then . So,
y³ = y · y² = y(-2y -4) = y(3y +1) = 3y² +4 = 3(3y +1)+y = (9y +y)+3 = 10y +3 = 3. Thus
3² ≡ 4 (mod 5). Also, (-3)² = 2² = 4.

3 Next Time

Prove that ≈ 50% of t’s will work. Solve quadratic equations for arbitrary n.