Number Theory Assignment #6 - Quadratic Congruences and Residues

This document presents solutions to a number theory assignment focusing on quadratic congruences and residues. The assignment includes problems that require the application of the quadratic formula, proving properties of quadratic residues, determining quadratic residues using the Legendre symbol, and exploring Euler's criterion and the Law of Quadratic Reciprocity. The solutions demonstrate the application of number theory concepts to solve various problems related to quadratic residues and congruences, providing a comprehensive guide for students studying number theory. The assignment covers topics such as solving quadratic equations modulo a prime, proving properties related to quadratic residues, and applying the Legendre symbol to determine if a number is a quadratic residue modulo another number. It also includes a proof related to the Law of Quadratic Reciprocity and finding square roots modulo a prime.

Running head: THEORY OF NUMBERS 1
Theory of Numbers
Firstname Lastname
Name of Institution

THEORY OF NUMBERS 2
Question 1
Solving using the quadratic formula
a. x2+ 26 x+ 48 ≡0 ( mod 149 )
x2+26 x+48 ≡0 ( mod 149 )
solution
z2 ≡ b2−4 ac ≡262 − ( 4 x 1 x 48 )
therefore by solving the solutionthe solution for x becomes
x ≡ 125 ,147 ( mod 149 )
b. 107 x2+128 x +56 ≡0 ( mod 211 )
107 x2+128 x +56 ≡0 ( mod 211 )
solution
z2 ≡ b2−4 ac ≡1282− ( 4 x 107 x 56 ) ≡16384−23968
by inspection, the equation has no solution .
c. 98 x2+ 31 x +329 ≡0 ( mod 431 )
98 x2+ 31 x +329 ≡0 ( mod 431 )
solution
z2 ≡ b2−4 ac ≡312− ( 4 x 98 x 329 ) ≡ 961−128968 ≡0 ( mod 431 )
Therefore the equation has one solutionfor x ,
x ≡ 90( mod 431)
Question 2
Proving that -1 is quadratic residue modulo p if
p ≡1 ( mod 4 )∧−1 is a quadratic nonresidue modulo p if p ≡ 3 ( mod 4 )
Proof,

THEORY OF NUMBERS 3
In this case the idea is to make an observation on -1 is a square residue mod p only if p ≡1 ¿.
Note that this is a standard theorem
Assuming the above results hold the first case goes
p ≡1 ( mod 4 ) … … … … … … … … … … … … … … case1
We have a≡ b2 ( mod p ) ∧−1 ≡ c2 ( modp ) … … ..considering results above
( −a ) = ( a ) ( −1 ) ≡ ( bc ) 2 mod ( p )
−a is confirmed ¿ be a square reside mod p∈this scenario
Considering case 2 we have
p ≡3 ( mod 4 ) … … … … … … … … … … … … .. for case2
By making an assumption that botha∧−a be square residue for mod p
¿ other other termsis assumed that a is not 0( mod p)
we have−1 ≡ ( −a ) ( ( a )−1 ) ( mod p ) ¿ be a square residue
thus by contradiction of the above results
therefore ( −a ) is not a square residue ( mod p ) ∈this proof ,
but only for quadratic residue for nonresidue modulo p if ∧only if p ≡ 3 ( mod 4 ) thus proof .
Question 3
Determining whether n is a quadratic residue modulo p
a. n = 278 and p = 467.
Solution
In this case we won’t all the quadratic residues mod 467 instead the proving for quadratic residue
for 278 ≡(467) by applying the Legendre symbols we start by stating
278=2 x 139

THEORY OF NUMBERS 4
We can therefore express∈the form of : 278
467 = 2
467 x 139
467
Subsequently 467 ≡3 mod 8is clear that the first Legendre symbol is−1.
Additionally , meanwhile 139 ≡ 467 ≡3 mod 4 , quadratic reciprocity shows that ,
139
467 =− ( 467
139 )We then get
2
467 x 139
467 = (−1 ) x ( −467
139 )= 467
139
2
467 x 139
467 =(−1)x (−467
139 )= 467
139
The new Legendre symbol is computed by reducing 467 modulo139
This is reduced ¿ 467 ≡50 mod 139
Therefore ,becomes 467
139 = 50
139 = 2
139 x 25
139
The second Legendre symbol is1 as 25is perfect square of 5
For the Legendre symbol having 2 , we state that ,
139 ≡3 mod 8 suggests that 2 cannot be a square mod 139.
Therefore ,results into , 2
139 x 25
139 = (−1 ) x (1)=−1
We can observe that 278 isnot a square mod 467∧,

THEORY OF NUMBERS 5
thus 278is not a quadratic residue modulo 467
b. n= 141 and p = 877
Solution
proving for quadratic residue for 141 ≡(mod 877) by applying the Legendre symbols we start by
stating that
141=3 x 47
We can therefore express∈the form of : 141
877 = 3
467 x 47
877
Subsequently 877 ≡ 5 mod 8is clear that the first Legendre symbol is 1.
Additionally , meanwhile 47 ≡877 ≡1 mod 4 , quadratic reciprocity shows that ,
47
877 =( 877
47 )We then get
3
877 x 47
877 = ( 1 ) x ( 877
47 )= 877
47
The new Legendre symbol is computed by reducing 877 modulo 47
Thisis reduced ¿ 87≡ 31 mod 47
Therefore ,becomes 877
47 = 31
47 =1

THEORY OF NUMBERS 6
Therefore ,results into , 31
47 = ( 1 ) x( 1)=1
We can observe that 141is a square mod 877∧,
thus 141is a quadratic residuemodulo 877
c. n = 344 and p = 619
Solution
Proving for quadratic residue for 344 ≡(mod 619) by applying the Legendre symbols we start by
stating that
344=23 x 43
We can therefore express∈the form of : 344
619 = 8
619 x 43
619
Subsequently 619 ≡3 mod 8is clear that the first Legendre symbol is−1.
Additionally , meanwhile 43≡ 619 ≡3 mod 4 , quadratic reciprocity shows that ,
43
619 =( 619
43 )We then get
8
619 x 43
619 = ( 1 ) x ( 619
43 )= 619
43
The new Legendre symbol is computed by reducing 619 modulo 43
Thisis reduced ¿ 619 ≡17 mod 47

THEORY OF NUMBERS 7
Therefore ,becomes 619
43 = 17
47 =1
Therefore ,results into , 17
43 = ( 1 ) x (1)=1
We can observe that 344 is a square mod 619∧,
thus 344 is a quadratic residue modulo 619
Question 4
a. Proving for that all odd prime divisors of n2 +1 are of the form 4 k +1 for n greater than 1
For instance a case where p is an odd prime ,
x2+I ≡0 (mod p)Will only have a solution if thecondition remains¿ be that p ≡1(mod 4).
That is , n as an integer satisfies theexpression for x2 +1 0 ( mod p ) ,
if ∧only if p=4 k +1.
p ≡1(mod 4)⟹ 4( p — I )
⟹ p=4 k + I , for approximately integer k .
¿ other words , p=4 k +1if ∧only if n2+1 ≡ 0 ( mod p ) for some integers k∧n .
Therefore the odd primedivisors of theinteger n2+1 are of the form 4 k +1.
Question 4b
Proof
Assumethat p 1 ,… , pn consisted ∈the primes ∈the form of 4 n+1.

THEORY OF NUMBERS 8
By letting M = ( 2 p 1 … pn ) 2+1.
M is not a divisor of 2∧has no multiplesof p 1 ,… … …. , pn
Since p 1 , … , pn are all the primes of the form 4 n+1 , all the prime
factors of M must therefore be of the form 4 n+3.
By taking p ¿ be one of these prime factors .
Therefore we have , ( 2 p1 … pn ) 2 +1≡ 0 mod p
Thus 2 ( p 1 ... pn )2 ≡−1 mod p .
Thisis an indication that−1is a quadratic residue mod p .
Otherwise−1 is a quadratic residue mod p if ∧only if p≡ 1 mod 4 , which is a contradiction .
Therefore , there must be a prime of the form 4 k +1that is bigger than pn .
So ,there are infinitely many primes of the form 4 k +1
Question 5
Solution
Showing that M ≡1(mod p)if p ≡ 3(mod 4)∧that M ≡1(mod p)if p ≡1(mod 4)
In this scenario we will consider a solution in the form
This can be written in the form of
Applying Euler’s criterion we find
Therefore, the solution reads as
The same criteria apply for

THEORY OF NUMBERS 9
M ≡ 1(mod p)if p ≡1(mod 4)
Therefore the proof confirms that
if M ≡1(mod p)if p ≡ 3(mod 4)∧that M ≡1(mod p) if p ≡1(mod 4)
Question 6
a. Deriving for formula for computing the square root for a (mod P)
Solution
¿ the provided expression , p ≡3 ( mod 4 ) can be expressed as below
p=3+ 4 ( k ) … … … … … … … … … … … … … … … … … … equation 1
Since x ≡1 mod N is equal ¿ the value of x=1+kN
Noting that that the value k ,is an integer
by adding 1 on both side of the first equation we have ,
p+1= ( 4 ( k )+ 3 ) +1
p+1= ( 4 ( k ) + 4 )
p+1=4 ( k +1 )
p+ 1
4 = ( k +1 ) … … … … … … … … … … … … … … … equation 2
Since k is an integer as stated above , when1 is added ( k +1 ) alsois an integer
¿ the equation 2, the value of ( k +1 ) is equal¿ p +1
4 , thereforeis aninteger .
Therefore the formula for computing the square root for a ( mod P ) is
x ≡ ± k
N +1
2 ≡± a
p+ 1
4 ( mod p )
b. Finding the square roots of 1467 (mod 2531)
Solution

THEORY OF NUMBERS
10
Using the formula derived above, we have the square root given by
x ≡ ± k
N +1
2 ≡± 1467
2531+1
4 ( mod 2531 )
the square root becomes=±1467633 ( mod 2531 )
c. Providing proof for getting square root for a (mod p)
Considering the case∈which p=8 k +5 ,
we commence by applying EulersCriterion , whereby we state
a
p−1
2 ≡1 ( mod p ) ,
therefore , a
p−1
4 ≡ ±1 ( mod p ) .
When a
p−1
4 ≡1 ( mod p ) therby setting x ≡ ak +1 ( mod p ) we find a solution
of which x2 ≡ a2 k +2 ≡ a
p+ 3
4 ≡ a
p−1
4 x a ≡a ( mod p )
if incase a
p −1
4 ≡−1 ( mod p ) , so x ≡ 22 k+1 ak+ 1 ( mod p ) givethe answer
therefore this is a proof
d. Finding square root of 498 (mod 2621).
x ≡ ± k
N +1
2 ≡± 498
2 621 +1
4 ( mod 2621 )
the square root becomes=± 498655.5 ( mod 2621 )

THEORY OF NUMBERS
11
References
Niven, I., Zuckerman, H. S., & Montgomery, H. L. (2014). An introduction to the theory of
numbers. John Wiley & Sons.
Silverman, J. H. (2016). A friendly introduction to number theory. Upper Saddle River, NJ:
Pearson Prentice Hall.