Basic Number Theory 18: quadratic equations modulo n

Nick · 2017-02-22, 13:08

Take any real numbers $a,b,c$ with $a\neq 0$, and suppose we wish to find all real numbers $x$ for which $ax^2+bx+c=0$.
As $a\neq 0$, we can divide by it throughout, getting $x^2+\frac{b}{a}x+\frac{c}{a}=0$.
In other words, the values of $x$ satisfying this equation are the same as those satisfying the original one.
We now use a trick known as completing the square: if we add $\left(\frac{b}{2a}\right)^2$ to both sides of the equation, they remain equal so
\[ x^2+\frac{b}{a}x+\left(\frac{b}{2a}\right)^2+\frac{c}{a}=
\left(\frac{b}{2a}\right)^2. \]
The point of this is that the first 3 terms on the left are now what we get if we multiply out the bracket in $\left(x+\frac{b}{2a}\right)^2$, so we may write the equation as
\[ \left(x+\frac{b}{2a}\right)^2+\frac{c}{a}=\left(\frac{b}{2a}\right)^2. \]
Now that $x$ only appears once, it is not difficult to write it in terms of $a,b$ and $c$: we have
\[\left(x+\frac{b}{2a}\right)^2=\left(\frac{b}{2a}\right)^2-\frac{c}{a}
=\frac{b^2-4ac}{4a^2} \]
so
\[x+\frac{b}{2a}=\pm\sqrt{\frac{b^2-4ac}{4a^2}}
=\frac{\pm\sqrt{b^2-4ac}}{2a} \]
hence
\[x=\frac{-b\pm\sqrt{b^2-4ac}}{2a} \]
which is the familiar formula for the solutions of the quadratic equation we started with.
The number $b^2-4ac$ is called the discriminant of the polynomial $ax^2+bx+c$.
If it is positive, then there are 2 distinct values of $x$ satisfying the equation.
If it is zero, then there is just 1 value for $x$, and if it is negative then there are no real values for $x$ (just 2 complex ones).

Now let $n$ be a positive integer and $a,b,c$ integers with $a\not\equiv 0\pmod{n}$, and suppose we wish to find all integers $x$ for which $ax^2+bx+c\equiv 0\pmod{n}$.
We cannot simply use the above formula: while addition, subtraction and multiplication in the integers modulo $n$ obey all the usual rules of arithmetic,
we cannot always divide by $2a$ (or even by 2 if $n$ is even) let alone take a square root.
In theory, we could simply try each value of $x$ from 0 to $n-1$ inclusive in turn, but that is not very efficient unless $n$ is quite small.
Instead, we need to understand the units and quadratic residues in the integers modulo $n$.
Fortunately, we have already done most of the work - all that remains is to determine which units are squares modulo a prime power,
and then we shall be able to tackle the problem systematically.

As usual, we have to treat the prime number 2 separately.

Proposition 105
Let $p$ be an odd prime number and $m$ a positive integer.
Then, for any integer $a$ not divisible by $p$,
$\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*$ is a square if and only if $\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ is a square.

proof
By proposition 95, the unit group $(\mathbb{Z}/p^m\mathbb{Z})^*$ of the integers modulo $p^m$ is cyclic, so there exists an integer $d$ such that
\[ \left(\mathbb{Z}/p^m\mathbb{Z}\right)^*
=\{\bar{d}^0=\bar{1},\bar{d}^1=\bar{a},
\bar{d}^2,\bar{d}^3,\ldots, \bar{d}^{(p-1)p^{m-1}-1}\} \]
with $\bar{d}^{(p-1)p^{m-1}}=\bar{1}$.
As $p$ is odd (and $m\geq 1$), this is a cylic group of even order so, by proposition 86, the powers of $\bar{d}^2$ form a cyclic subgroup containing exactly half of the elements,
and these are precisely the squares in $(\mathbb{Z}/p^m\mathbb{Z})^*$.
Let $f:(\mathbb{Z}/p^m\mathbb{Z})^*\rightarrow (\mathbb{Z}/p\mathbb{Z})^*$ be the function sending $\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^*$ to $\bar{n}\in (\mathbb{Z}/p\mathbb{Z})^*$
(equivalently, $f(n\bmod{p^m})=n\bmod{p}$).
We must check that this is well-defined.
For any integer $n$, if $n\bmod{p^m}$ is a unit in the integers modulo $p^m$ then $\gcd(n,p^m)=1$ so $\gcd(n,p)=1$ as well,
hence $n\bmod{p}$ is a unit in the integers modulo $p$.
And, for any integers $m,n$, if $\bar{m}=\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^*$ then $p^m$ divides $m-n$
so $p$ divides $m-n$ too, and therefore $\bar{m}=\bar{n}\in(\mathbb{Z}/p\mathbb{Z})^*$.
Thus $f$ is well-defined.
Conversely, for any integer $n$, if $n\bmod{p}$ is a unit in the integers modulo $p$ then $\gcd(n,p)=1$
so $\gcd(n,p^m)=1$ and $n\bmod{p^m}$ is a unit in the integers modulo $p^m$.
Hence $f$ is surjective.
Moreover, for any integer $n$, $f(\bar{d}^n)=(f(\bar{d}))^n$ so $f(\bar{d})$ generates the whole cyclic group $(\mathbb{Z}/p\mathbb{Z})^*$.
In the same way as before, the powers of $f(\bar{d})^2$ form a cyclic subgroup containing exactly half the elements,
and these are precisely the squares in $(\mathbb{Z}/p\mathbb{Z})^*$.
Thus $f$ maps squares in $(\mathbb{Z}/p^m\mathbb{Z})^*$ to squares in $(\mathbb{Z}/p\mathbb{Z})^*$, and non-squares to non-squares.
It follows that, for any integer $a$ not divisible by $p$, $\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*$ is a square if and only if $\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ is a square. ∎

Proposition 106
Let $a,m$ be integers such that $a$ is odd and $m\geq 3$.
Then $\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^*$ is a square if and only if $a\equiv 1\pmod{8}$.

proof
By proposition 96,
\[ \left(\mathbb{Z}/2^m\mathbb{Z}\right)^*=
\{(-\bar{1})^i\bar{5}^j:i,j\in\mathbb{Z}\} \]
and, for all integers $i,j,k,l$,
\[ (-\bar{1})^i\bar{5}^j=(-\bar{1})^{k}\bar{5}^{l}\Leftrightarrow
2|i-k\mbox{ and }2^{m-2}|j-l. \]

Suppose $a\equiv 1\pmod{8}$.
We have $a\equiv (-1)^r5^s\pmod{2^m}$ for some integers $r,s$, and $m\geq 3$ so $(-1)^r5^s\equiv 1\pmod{8}$.
As $5^2\equiv 1\pmod{8}$ but $\pm5\not\equiv 1\pmod{8}$,
it follows that $r$ and $s$ are both even, making $\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^*$ a square.

Suppose instead that $\bar{a}$ is a square.
Then there exist integers $i,j$ such that $((-1)^i5^j)^2\equiv a\pmod{2^m}$.
And $m\geq 3$ so $a\equiv (-1)^{2i}5^{2j}\equiv 1\pmod{8}$. ∎

Before we can tackle quadratic equations modulo $n$, we need to be able to
solve linear equations and determine the existence of square roots.

LINEAR EQUATIONS
Let $n$ be a positive integer, $a,b$ integers with $a\not\equiv 0\pmod{n}$
and suppose we wish to find all integers $x$ such that
\[ ax+b\equiv 0\pmod{n}. \]
Let $d=\gcd(a,n)$.
If $d=1$ then there exists an integer $u$ such that $au\equiv 1\pmod{n}$ (which can be found with the Euclidean algorithm)
so $ax+b\equiv 0\pmod{n}$ if and only if $x\equiv -bu\pmod{n}$.
Suppose $d>1$.
Then $a=da'$ and $n=dn'$ for some integers $a',n'$.
If there exists an integer $x$ with $ax+b\equiv 0\pmod{n}$ then $b\equiv -da'x\pmod{dn'}$ so $d|b$.
Thus is $b$ is not divisible by $d$ then there are no solutions.
If $b$ is divisible by $d$ then $b=db'$ for some integer $b'$ and, for all integers $x$,
$ax+b\equiv 0\pmod{n}$ if and only if $a'x+b'\equiv 0\pmod{n'}$.
Moreover, $\gcd(a',n')=1$, so we can proceed as in the first case.

EXISTENCE OF SQUARE ROOTS
Let $n$ be a positive integer, $c$ an integer and suppose we wish to determine whether an integer $x$ exists such that $x^2\equiv c\pmod{n}$.
Let $d=\gcd(c,n)$, and suppose first that $d=1$.
We assume that $n$ is small enough to be factorized completely: write $n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}$
where $k$ is a non-negative integer, $p_1,p_2,\ldots,p_k$ are distinct prime numbers and $e_1,e_2,\ldots,e_k$ are positive integers.
By the Chinese Remainder Theorem, there exists an integer $x$ such that $x^2\equiv c\pmod{n}$ if and only if, for each $i\in\{1,2,\ldots,k\}$, there exists an integer $x_i$ with $x_i^2\equiv c\pmod{p_i^{e_i}}$
(and the possible values of $x$ can then be constructed from all combinations of $x_1,x_2,\ldots,x_k$).
Take any $i\in\{1,2,\ldots,k\}$.
If $p_i\neq 2$ then $c$ is a square modulo $p_i^{e_i}$ if and only if $c$ is a square modulo $p_i$ by proposition 105,
and $p_i$ does not divide $c$ (since $d=1$) so this holds if and only if $(\frac{c}{p_i})=1$, which we can determine using the quadratic reciprocity law (corollary 104).
Suppose instead $p_i=2$.
If $e_i=1$ then $c$ is a square modulo 2.
If $e_i=2$ then $c$ is a square modulo 4 if and only if $c\equiv 1\pmod{4}$ (in this case, $n$ is even so $c$ is odd).
And if $e_i\geq 3$ then $c$ is a square modulo $2^{e_i}$ if and only if $c\equiv 1\pmod{8}$ by proposition 106.
This covers all cases where $d=1$.

Now suppose that $d>1$.
Write $d=r^2s$ where $r,s$ are integers with $r$ as large as possible.
In other words, $s$ is a product of distinct prime numbers, namely those occurring to an odd power in the prime factorization of $d$.
Thus $s$ is not divisible by the square of any number greater than 1 - we call s square-free.
There exist integers $c',n'$ such that $c=dc'$ and $n=dn'$.
For any integer $x$, if $x^2\equiv c\pmod{n}$ then $r^2s|x^2$ and $s$ is square-free so $rs|x$.
Thus $x=rsy$ for some integer $y$ and $(rsy)^2\equiv r^2sc'\pmod{r^2sn'}$ so $sy^2\equiv c'\pmod{n'}$.
Any prime number dividing both $s$ and $n'$ also divides $c'$, but $\gcd(c',n')=1$ so $\gcd(s,n')=1$ too
and therefore there exists an integer $u$ with $su\equiv 1\pmod{n'}$.
Thus $y^2\equiv c'u\pmod{n'}$, and $\gcd(c'u,n')=1$ so we can proceed as in the case where $d=1$.

Note that the above determines whether a square root of $c$ exists in the integers modulo $n$, but not how to find it.
General solutions to this problem use mathematics that we have not yet covered.
For small powers of small primes, however, trial and error will suffice,
and there are other special cases in which it is straightforward as well (see exercises 83 and 86 below).

QUADRATIC EQUATIONS
Let $n$ be a positive integer and $a,b,c$ integers with $a\not\equiv 0\pmod{n}$, and suppose we wish to find all integers $x$ for which
\[ ax^2+bx+c\equiv 0\pmod{n}. \]
We cannot necessarily divide by $a$ to complete the square, so we multiply throughout by $4a$ instead, getting $4a^2x^2+4abx+4ac\equiv 0\pmod{4an}$, and write this as a square:
\[ (2ax+b)^2\equiv b^2-4ac\pmod{4an}. \]
Using the above method for square roots, we may determine whether $b^2-4ac$ is a square in the integers modulo $4an$ and,
if so, we can take each integer $y$ with $y^2\equiv b^2-4ac\pmod{4an}$ and use the above method for linear equations to solve $2ax+b\equiv y\pmod{4an}$.

Exercises
83. Let $p$ be a prime number with $p\equiv 3\pmod{4}$, $c$ an integer which is a square modulo $p$, and $x\equiv c^{\frac{p+1}{4}}\pmod{p}$.
Show that $x^2\equiv c\pmod{p}$.
84. Find all integers $x$ such that $12x+24\equiv 0\pmod{33}$.
85. Find all integers $x$ such that $3x^2+6x+5\equiv 0\pmod{7}$.
86. Let $p$ be a prime number with $p\equiv 5\pmod{8}$ and $c$ an integer which is a square modulo $p$.
Let $x,y$ be integers such that $x\equiv c^{\frac{p+3}{8}}\pmod{p}$ and $y\equiv 2^{\frac{p-1}{4}}\pmod{p}$.
Show that $x^2\equiv\pm c\pmod{p}$ and $y^2\equiv -1\pmod{p}$.
Conclude that $x$ or $xy$ is a square root of $c$ modulo $p$.

MattcAnderson · 2017-02-25, 23:00

Hi Mersenneforum,

In order to tackle this first number theory problem,
(okay it is problem 84)
I will try a similar problem.
Find all x such that
5*x+6 is congruent to 0 mod 7 expression 1

From the reading, I notice that the greatest common divisor of 5 and 6 is 1. So the techniques presented here should apply.

We make an augmented T table

X 5*X 5*X mod 7
______________________
0 0 0
1 5 5
2 10 3
3 15 1
4 20 6
5 25 4
6 30 2

From expression 1, conclude that 5*x is congruent to 1 mod 7.
My education has a gap here.

I use my Maple computer tool to conclude that x is congruent to 2*x+1 mod 7.
Here is my Maple code –

a:=-(5*x+6) mod 7

And, again, Maple returns a= 2*x+1 mod 7.
Maybe someone can help me fill in the gaps.
Regards,
Matt

science_man_88 · 2017-02-25, 23:20

Quote:

Originally Posted by MattcAnderson

Hi Mersenneforum,

In order to tackle this first number theory problem,
(okay it is problem 84)
I will try a similar problem.
Find all x such that
5*x+6 is congruent to 0 mod 7 expression 1

From the reading, I notice that the greatest common divisor of 5 and 6 is 1. So the techniques presented here should apply.

We make an augmented T table

X 5*X 5*X mod 7
______________________
0 0 0
1 5 5
2 10 3
3 15 1
4 20 6
5 25 4
6 30 2

From expression 1, conclude that 5*x is congruent to 1 mod 7.
My education has a gap here.

I use my Maple computer tool to conclude that x is congruent to 2*x+1 mod 7.
Here is my Maple code –

a:=-(5*x+6) mod 7

And, again, Maple returns a= 2*x+1 mod 7.
Maybe someone can help me fill in the gaps.
Regards,
Matt

$5x+6 \equiv 0 \pmod 7\\ 5x\equiv -6 \pmod 7 \\ 5\equiv -2 \pmod 7 \\ \therefore \\ 5x\equiv -2x \pmod 7 \\ -6 \equiv -2x\pmod 7 \\ 3 \equiv x \pmod 7 \\ $

but this equation isn't quadratic.

edit:

the solution like this for 84 is similar to this:

$\text {deleted previous ramble after checking with PARI/GP} \\ 12x+24 \equiv 0 \pmod {33} \\ 3(4x+8)\equiv 0 \pmod {3(11)}\\ (4x+8)\equiv 0 \pmod {11}\\ 4(x+2)\equiv 0 \pmod {11}\\ \text { by 0 product rule one of these has to be 0 and 4 is not 0} \\ x+2 \equiv 0 \pmod {11}\\ x\equiv -2 \pmod {11}\\ x \equiv 9 \pmod {11}\\ $

Nick · 2017-02-26, 10:09

Quote:

Originally Posted by MattcAnderson

Find all x such that
5*x+6 is congruent to 0 mod 7 expression 1

From the reading, I notice that the greatest common divisor of 5 and 6 is 1. So the techniques presented here should apply.

We make an augmented T table

X 5*X 5*X mod 7
______________________
0 0 0
1 5 5
2 10 3
3 15 1
4 20 6
5 25 4
6 30 2

From expression 1, conclude that 5*x is congruent to 1 mod 7.

Yes, and only one row in your table has 5x mod 7 = 1...

An alternative approach is to multiply by 3 (because 3x5 mod 7=1):
if $5x+6\equiv 0\pmod{7}$ then $3(5x+6)\equiv 0\pmod{7}$
and so $x+4\equiv 0\pmod{7}$.

I hope this helps!

MattcAnderson · 2017-03-27, 06:01

Hi Mersenneforum and Nick,

Thank you for the instruction about linear equations with a modulus.
It helps.

Regards,
Matt

2017-02-22, 13:08	#1
Nick Dec 2012 The Netherlands 2×3×307 Posts	Basic Number Theory 18: quadratic equations modulo n Take any real numbers \(a,b,c\) with \(a\neq 0\), and suppose we wish to find all real numbers \(x\) for which \(ax^2+bx+c=0\). As \(a\neq 0\), we can divide by it throughout, getting \(x^2+\frac{b}{a}x+\frac{c}{a}=0\). In other words, the values of \(x\) satisfying this equation are the same as those satisfying the original one. We now use a trick known as completing the square: if we add \(\left(\frac{b}{2a}\right)^2\) to both sides of the equation, they remain equal so \[ x^2+\frac{b}{a}x+\left(\frac{b}{2a}\right)^2+\frac{c}{a}= \left(\frac{b}{2a}\right)^2. \] The point of this is that the first 3 terms on the left are now what we get if we multiply out the bracket in \(\left(x+\frac{b}{2a}\right)^2\), so we may write the equation as \[ \left(x+\frac{b}{2a}\right)^2+\frac{c}{a}=\left(\frac{b}{2a}\right)^2. \] Now that \(x\) only appears once, it is not difficult to write it in terms of \(a,b\) and \(c\): we have \[\left(x+\frac{b}{2a}\right)^2=\left(\frac{b}{2a}\right)^2-\frac{c}{a} =\frac{b^2-4ac}{4a^2} \] so \[x+\frac{b}{2a}=\pm\sqrt{\frac{b^2-4ac}{4a^2}} =\frac{\pm\sqrt{b^2-4ac}}{2a} \] hence \[x=\frac{-b\pm\sqrt{b^2-4ac}}{2a} \] which is the familiar formula for the solutions of the quadratic equation we started with. The number \(b^2-4ac\) is called the discriminant of the polynomial \(ax^2+bx+c\). If it is positive, then there are 2 distinct values of \(x\) satisfying the equation. If it is zero, then there is just 1 value for \(x\), and if it is negative then there are no real values for \(x\) (just 2 complex ones). Now let \(n\) be a positive integer and \(a,b,c\) integers with \(a\not\equiv 0\pmod{n}\), and suppose we wish to find all integers \(x\) for which \(ax^2+bx+c\equiv 0\pmod{n}\). We cannot simply use the above formula: while addition, subtraction and multiplication in the integers modulo \(n\) obey all the usual rules of arithmetic, we cannot always divide by \(2a\) (or even by 2 if \(n\) is even) let alone take a square root. In theory, we could simply try each value of \(x\) from 0 to \(n-1\) inclusive in turn, but that is not very efficient unless \(n\) is quite small. Instead, we need to understand the units and quadratic residues in the integers modulo \(n\). Fortunately, we have already done most of the work - all that remains is to determine which units are squares modulo a prime power, and then we shall be able to tackle the problem systematically. As usual, we have to treat the prime number 2 separately. Proposition 105 Let \(p\) be an odd prime number and \(m\) a positive integer. Then, for any integer \(a\) not divisible by \(p\), \(\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^\) is a square if and only if \(\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^\) is a square. proof By proposition 95, the unit group \((\mathbb{Z}/p^m\mathbb{Z})^\) of the integers modulo \(p^m\) is cyclic, so there exists an integer \(d\) such that \[ \left(\mathbb{Z}/p^m\mathbb{Z}\right)^ =\{\bar{d}^0=\bar{1},\bar{d}^1=\bar{a}, \bar{d}^2,\bar{d}^3,\ldots, \bar{d}^{(p-1)p^{m-1}-1}\} \] with \(\bar{d}^{(p-1)p^{m-1}}=\bar{1}\). As \(p\) is odd (and \(m\geq 1\)), this is a cylic group of even order so, by proposition 86, the powers of \(\bar{d}^2\) form a cyclic subgroup containing exactly half of the elements, and these are precisely the squares in \((\mathbb{Z}/p^m\mathbb{Z})^\). Let \(f:(\mathbb{Z}/p^m\mathbb{Z})^\rightarrow (\mathbb{Z}/p\mathbb{Z})^\) be the function sending \(\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^\) to \(\bar{n}\in (\mathbb{Z}/p\mathbb{Z})^\) (equivalently, \(f(n\bmod{p^m})=n\bmod{p}\)). We must check that this is well-defined. For any integer \(n\), if \(n\bmod{p^m}\) is a unit in the integers modulo \(p^m\) then \(\gcd(n,p^m)=1\) so \(\gcd(n,p)=1\) as well, hence \(n\bmod{p}\) is a unit in the integers modulo \(p\). And, for any integers \(m,n\), if \(\bar{m}=\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^\) then \(p^m\) divides \(m-n\) so \(p\) divides \(m-n\) too, and therefore \(\bar{m}=\bar{n}\in(\mathbb{Z}/p\mathbb{Z})^\). Thus \(f\) is well-defined. Conversely, for any integer \(n\), if \(n\bmod{p}\) is a unit in the integers modulo \(p\) then \(\gcd(n,p)=1\) so \(\gcd(n,p^m)=1\) and \(n\bmod{p^m}\) is a unit in the integers modulo \(p^m\). Hence \(f\) is surjective. Moreover, for any integer \(n\), \(f(\bar{d}^n)=(f(\bar{d}))^n\) so \(f(\bar{d})\) generates the whole cyclic group \((\mathbb{Z}/p\mathbb{Z})^\). In the same way as before, the powers of \(f(\bar{d})^2\) form a cyclic subgroup containing exactly half the elements, and these are precisely the squares in \((\mathbb{Z}/p\mathbb{Z})^\). Thus \(f\) maps squares in \((\mathbb{Z}/p^m\mathbb{Z})^\) to squares in \((\mathbb{Z}/p\mathbb{Z})^\), and non-squares to non-squares. It follows that, for any integer \(a\) not divisible by \(p\), \(\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^\) is a square if and only if \(\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^\) is a square. ∎ Proposition 106 Let \(a,m\) be integers such that \(a\) is odd and \(m\geq 3\). Then \(\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^\) is a square if and only if \(a\equiv 1\pmod{8}\). proof By proposition 96, \[ \left(\mathbb{Z}/2^m\mathbb{Z}\right)^= \{(-\bar{1})^i\bar{5}^j:i,j\in\mathbb{Z}\} \] and, for all integers \(i,j,k,l\), \[ (-\bar{1})^i\bar{5}^j=(-\bar{1})^{k}\bar{5}^{l}\Leftrightarrow 2\|i-k\mbox{ and }2^{m-2}\|j-l. \] Suppose \(a\equiv 1\pmod{8}\). We have \(a\equiv (-1)^r5^s\pmod{2^m}\) for some integers \(r,s\), and \(m\geq 3\) so \((-1)^r5^s\equiv 1\pmod{8}\). As \(5^2\equiv 1\pmod{8}\) but \(\pm5\not\equiv 1\pmod{8}\), it follows that \(r\) and \(s\) are both even, making \(\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^\) a square. Suppose instead that \(\bar{a}\) is a square. Then there exist integers \(i,j\) such that \(((-1)^i5^j)^2\equiv a\pmod{2^m}\). And \(m\geq 3\) so \(a\equiv (-1)^{2i}5^{2j}\equiv 1\pmod{8}\). ∎ Before we can tackle quadratic equations modulo \(n\), we need to be able to solve linear equations and determine the existence of square roots. LINEAR EQUATIONS Let \(n\) be a positive integer, \(a,b\) integers with \(a\not\equiv 0\pmod{n}\) and suppose we wish to find all integers \(x\) such that \[ ax+b\equiv 0\pmod{n}. \] Let \(d=\gcd(a,n)\). If \(d=1\) then there exists an integer \(u\) such that \(au\equiv 1\pmod{n}\) (which can be found with the Euclidean algorithm) so \(ax+b\equiv 0\pmod{n}\) if and only if \(x\equiv -bu\pmod{n}\). Suppose \(d>1\). Then \(a=da'\) and \(n=dn'\) for some integers \(a',n'\). If there exists an integer \(x\) with \(ax+b\equiv 0\pmod{n}\) then \(b\equiv -da'x\pmod{dn'}\) so \(d\|b\). Thus is \(b\) is not divisible by \(d\) then there are no solutions. If \(b\) is divisible by \(d\) then \(b=db'\) for some integer \(b'\) and, for all integers \(x\), \(ax+b\equiv 0\pmod{n}\) if and only if \(a'x+b'\equiv 0\pmod{n'}\). Moreover, \(\gcd(a',n')=1\), so we can proceed as in the first case. EXISTENCE OF SQUARE ROOTS Let \(n\) be a positive integer, \(c\) an integer and suppose we wish to determine whether an integer \(x\) exists such that \(x^2\equiv c\pmod{n}\). Let \(d=\gcd(c,n)\), and suppose first that \(d=1\). We assume that \(n\) is small enough to be factorized completely: write \(n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}\) where \(k\) is a non-negative integer, \(p_1,p_2,\ldots,p_k\) are distinct prime numbers and \(e_1,e_2,\ldots,e_k\) are positive integers. By the Chinese Remainder Theorem, there exists an integer \(x\) such that \(x^2\equiv c\pmod{n}\) if and only if, for each \(i\in\{1,2,\ldots,k\}\), there exists an integer \(x_i\) with \(x_i^2\equiv c\pmod{p_i^{e_i}}\) (and the possible values of \(x\) can then be constructed from all combinations of \(x_1,x_2,\ldots,x_k\)). Take any \(i\in\{1,2,\ldots,k\}\). If \(p_i\neq 2\) then \(c\) is a square modulo \(p_i^{e_i}\) if and only if \(c\) is a square modulo \(p_i\) by proposition 105, and \(p_i\) does not divide \(c\) (since \(d=1\)) so this holds if and only if \((\frac{c}{p_i})=1\), which we can determine using the quadratic reciprocity law (corollary 104). Suppose instead \(p_i=2\). If \(e_i=1\) then \(c\) is a square modulo 2. If \(e_i=2\) then \(c\) is a square modulo 4 if and only if \(c\equiv 1\pmod{4}\) (in this case, \(n\) is even so \(c\) is odd). And if \(e_i\geq 3\) then \(c\) is a square modulo \(2^{e_i}\) if and only if \(c\equiv 1\pmod{8}\) by proposition 106. This covers all cases where \(d=1\). Now suppose that \(d>1\). Write \(d=r^2s\) where \(r,s\) are integers with \(r\) as large as possible. In other words, \(s\) is a product of distinct prime numbers, namely those occurring to an odd power in the prime factorization of \(d\). Thus \(s\) is not divisible by the square of any number greater than 1 - we call s square-free. There exist integers \(c',n'\) such that \(c=dc'\) and \(n=dn'\). For any integer \(x\), if \(x^2\equiv c\pmod{n}\) then \(r^2s\|x^2\) and \(s\) is square-free so \(rs\|x\). Thus \(x=rsy\) for some integer \(y\) and \((rsy)^2\equiv r^2sc'\pmod{r^2sn'}\) so \(sy^2\equiv c'\pmod{n'}\). Any prime number dividing both \(s\) and \(n'\) also divides \(c'\), but \(\gcd(c',n')=1\) so \(\gcd(s,n')=1\) too and therefore there exists an integer \(u\) with \(su\equiv 1\pmod{n'}\). Thus \(y^2\equiv c'u\pmod{n'}\), and \(\gcd(c'u,n')=1\) so we can proceed as in the case where \(d=1\). Note that the above determines whether a square root of \(c\) exists in the integers modulo \(n\), but not how to find it. General solutions to this problem use mathematics that we have not yet covered. For small powers of small primes, however, trial and error will suffice, and there are other special cases in which it is straightforward as well (see exercises 83 and 86 below). QUADRATIC EQUATIONS Let \(n\) be a positive integer and \(a,b,c\) integers with \(a\not\equiv 0\pmod{n}\), and suppose we wish to find all integers \(x\) for which \[ ax^2+bx+c\equiv 0\pmod{n}. \] We cannot necessarily divide by \(a\) to complete the square, so we multiply throughout by \(4a\) instead, getting \(4a^2x^2+4abx+4ac\equiv 0\pmod{4an}\), and write this as a square: \[ (2ax+b)^2\equiv b^2-4ac\pmod{4an}. \] Using the above method for square roots, we may determine whether \(b^2-4ac\) is a square in the integers modulo \(4an\) and, if so, we can take each integer \(y\) with \(y^2\equiv b^2-4ac\pmod{4an}\) and use the above method for linear equations to solve \(2ax+b\equiv y\pmod{4an}\). Exercises 83. Let \(p\) be a prime number with \(p\equiv 3\pmod{4}\), \(c\) an integer which is a square modulo \(p\), and \(x\equiv c^{\frac{p+1}{4}}\pmod{p}\). Show that \(x^2\equiv c\pmod{p}\). 84. Find all integers \(x\) such that \(12x+24\equiv 0\pmod{33}\). 85. Find all integers \(x\) such that \(3x^2+6x+5\equiv 0\pmod{7}\). 86. Let \(p\) be a prime number with \(p\equiv 5\pmod{8}\) and \(c\) an integer which is a square modulo \(p\). Let \(x,y\) be integers such that \(x\equiv c^{\frac{p+3}{8}}\pmod{p}\) and \(y\equiv 2^{\frac{p-1}{4}}\pmod{p}\). Show that \(x^2\equiv\pm c\pmod{p}\) and \(y^2\equiv -1\pmod{p}\). Conclude that \(x\) or \(xy\) is a square root of \(c\) modulo \(p\).

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 1 & 2	Nick	Number Theory Discussion Group	17	2017-12-23 20:10
Basic Number Theory 20: polynomials	Nick	Number Theory Discussion Group	5	2017-04-25 14:32
Basic Number Theory 17: quadratic reciprocity	Nick	Number Theory Discussion Group	0	2017-01-31 14:41
Basic Number Theory 14: a first look at groups	Nick	Number Theory Discussion Group	0	2016-12-29 13:47
Basic Number Theory 13: Pythagorean triples and a few Diophantine equations	Nick	Number Theory Discussion Group	2	2016-12-18 14:49

2017-02-25, 23:00	#2
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1211₁₀ Posts	Hi Mersenneforum, In order to tackle this first number theory problem, (okay it is problem 84) I will try a similar problem. Find all x such that 5x+6 is congruent to 0 mod 7 expression 1 From the reading, I notice that the greatest common divisor of 5 and 6 is 1. So the techniques presented here should apply. We make an augmented T table X 5X 5X mod 7 ______________________ 0 0 0 1 5 5 2 10 3 3 15 1 4 20 6 5 25 4 6 30 2 From expression 1, conclude that 5x is congruent to 1 mod 7. My education has a gap here. I use my Maple computer tool to conclude that x is congruent to 2x+1 mod 7. Here is my Maple code – a:=-(5x+6) mod 7 And, again, Maple returns a= 2*x+1 mod 7. Maybe someone can help me fill in the gaps. Regards, Matt

2017-03-27, 06:01	#5
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 7×173 Posts	Hi Mersenneforum and Nick, Thank you for the instruction about linear equations with a modulus. It helps. Regards, Matt