Scribd
Upload
9 views2 pages

Homework 11

This document is an exercise sheet for a Number Theory and Cryptography course, focusing on quadratic residues. It includes five exercises that cover topics such as the properties of positive divisors, quadratic residues modulo primes, and the use of Euler's Criterion. The exercises aim to deepen understanding of number theory concepts and their applications in cryptography.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Homework 11

This document is an exercise sheet for a Number Theory and Cryptography course, focusing on quadratic residues. It includes five exercises that cover topics such as the properties of positive divisors, quadratic residues modulo primes, and the use of Euler's Criterion. The exercises aim to deepen understanding of number theory concepts and their applications in cryptography.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Number Theory and Cryptography

Math UN3020
New York, 2023/04/05

Exercise Sheet 11

Quadratic Residues

Exercise 1 (11 points). For an integer n, consider the set of positive divisors of n, defined as

Div+
n := { d ∈ Z | d > 0 AND d | n }.

Consider the function


τ (n) := #Div+
n .

Prove that, if m and n are coprime, we have

τ (mn) = τ (m)τ (n) .

Exercise 2 (11 points). Let p be a prime, and b ∈ Z be such that gcd(b, pα ) = ps > 1. Prove
that

1. If b ≡ 0 (mod pα ), then b is a quadratic residue modulo pα .

2. If b 6≡ 0 (mod pα ) and s is odd, then b is not a quadratic residue modulo pα .


b
3. If b 6≡ 0 (mod pα ) and s is even, then b is a quadratic residue modulo pα if and only if ps
is a quadratic residue modulo p.

(Hint:) Write the binomial equation x2 ≡ b (mod pα ) and apply the method for the case when
b is not invertible.

1
Exercise 3 (16 points). Use Euler’s Criterion to determine if the following are quadratic residues:

(a) 2 modulo 31.

(b) 2 modulo 43.

(c) 3 modulo 31.

(d) 7 modulo 29.

Exercise 4 (11 points). Let n be an even positive integer, and p be a prime such that p | n2 + 1.
Prove that
p ≡ 1 (mod 4) .
(Hint:) First, show that
n2
   
−1
= .
p p

Exercise 5 (11 points). Prove that there are infinitely many primes congruent to 1 modulo 4.
(Hint:) Write a proof similar to Euclid’s proof. Use Exercise 4.

You might also like