2. Use Gauss' Lemma, to compute (²) = (-1)², μ = |aPn N, -6 (30). 31
Elements Of Modern Algebra
8th Edition
ISBN:9781285463230
Author:Gilbert, Linda, Jimmie
Publisher:Gilbert, Linda, Jimmie
Chapter2: The Integers
Section2.5: Congruence Of Integers
Problem 58E: a. Prove that 10n(1)n(mod11) for every positive integer n. b. Prove that a positive integer z is...
Related questions
Question
[Number Theory] How do you solve question 2? The second picture is for definitions
![A more effective test for quadratic residues is given by Gauss's Lemma:
Theorem 7.9
If p is an odd prime and a € Up, then (‡) = (−1)ª where µ = |aP^N\.
Before proving this, let us consider an example:
Example 7.7
Let p = 19, so P = {1,2,...,9}, and let a = 11. If we multiply each element of
P by 11 mod (19), and then represent it by an element of PUN, we get
aP = 11P = {-8, 3, -5, 6, -2, 9, 1, -7,4}.
This contains four elements of N (the terms with minus signs), so μ = 4, which
is even; thus (1) = 1, so 11 € Q19. In fact, 11 = 7² mod (19).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fdb4b11dd-01c4-40d6-bd56-70e0f813edd6%2F1fa1a3be-c0f1-45b2-aa8d-ea451f4c30b8%2Fhm6t5ho_processed.png&w=3840&q=75)
Transcribed Image Text:A more effective test for quadratic residues is given by Gauss's Lemma:
Theorem 7.9
If p is an odd prime and a € Up, then (‡) = (−1)ª where µ = |aP^N\.
Before proving this, let us consider an example:
Example 7.7
Let p = 19, so P = {1,2,...,9}, and let a = 11. If we multiply each element of
P by 11 mod (19), and then represent it by an element of PUN, we get
aP = 11P = {-8, 3, -5, 6, -2, 9, 1, -7,4}.
This contains four elements of N (the terms with minus signs), so μ = 4, which
is even; thus (1) = 1, so 11 € Q19. In fact, 11 = 7² mod (19).
![1. Evaluate the following Legendre symbols:
2. Use Gauss' Lemma,
(i)
to compute
(ii)
(iii)
In (ii) p is an odd prime, p ‡ 7; in (iii) p is an odd prime p ‡ 3. In (ii) express the answer
in terms of a congruence condition on p mod 28, and in (iii) express the answer in terms of
a congruence condition on p mod 24, analogous to
= 1 if p = 1 mod 4 and -1 if p = 3 mod 4.
463
541
= (-1)",
4. For an odd prime p, suppose that
31
8933
104729
3. For an odd prime p≥ 7, show that there are consecutive quadratic residues mod p, i.e.,
that there exists an element a € Up such that
μ = |aPN,
a
(²) - ( ² + ¹) -
=
Hint: First show that at least one of the numbers 2, 5 and 10 is a quadratic residue mod p.
x =
a = 1 and consider the congruence
= 1.
=
x² = a mod p.
(i) For p = 3 + 4k, i.e., for p = 3 mod 4, show that the solutions to the congruence are
tak+1
or x =
1
(ii) For p = 5 + 8k, i.e., for p = 5 mod 8, show that the solutions to the congruence are
x = ±ak+¹,
+2²k+1 k+1
a
Explain how to see which is the correct choice.
(iii) Use the results of (i) and (ii) to find the solutions to the congruences
x² = 23 mod 751
x² = 15 mod 797](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fdb4b11dd-01c4-40d6-bd56-70e0f813edd6%2F1fa1a3be-c0f1-45b2-aa8d-ea451f4c30b8%2Fbdog64p_processed.png&w=3840&q=75)
Transcribed Image Text:1. Evaluate the following Legendre symbols:
2. Use Gauss' Lemma,
(i)
to compute
(ii)
(iii)
In (ii) p is an odd prime, p ‡ 7; in (iii) p is an odd prime p ‡ 3. In (ii) express the answer
in terms of a congruence condition on p mod 28, and in (iii) express the answer in terms of
a congruence condition on p mod 24, analogous to
= 1 if p = 1 mod 4 and -1 if p = 3 mod 4.
463
541
= (-1)",
4. For an odd prime p, suppose that
31
8933
104729
3. For an odd prime p≥ 7, show that there are consecutive quadratic residues mod p, i.e.,
that there exists an element a € Up such that
μ = |aPN,
a
(²) - ( ² + ¹) -
=
Hint: First show that at least one of the numbers 2, 5 and 10 is a quadratic residue mod p.
x =
a = 1 and consider the congruence
= 1.
=
x² = a mod p.
(i) For p = 3 + 4k, i.e., for p = 3 mod 4, show that the solutions to the congruence are
tak+1
or x =
1
(ii) For p = 5 + 8k, i.e., for p = 5 mod 8, show that the solutions to the congruence are
x = ±ak+¹,
+2²k+1 k+1
a
Explain how to see which is the correct choice.
(iii) Use the results of (i) and (ii) to find the solutions to the congruences
x² = 23 mod 751
x² = 15 mod 797
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 2 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Recommended textbooks for you
![Elements Of Modern Algebra](https://www.bartleby.com/isbn_cover_images/9781285463230/9781285463230_smallCoverImage.gif)
Elements Of Modern Algebra
Algebra
ISBN:
9781285463230
Author:
Gilbert, Linda, Jimmie
Publisher:
Cengage Learning,
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage
![Elements Of Modern Algebra](https://www.bartleby.com/isbn_cover_images/9781285463230/9781285463230_smallCoverImage.gif)
Elements Of Modern Algebra
Algebra
ISBN:
9781285463230
Author:
Gilbert, Linda, Jimmie
Publisher:
Cengage Learning,
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage