“Quadratic Residue”的概念、定义、习题解题方法及翻译-数学辞典

单词

Quadratic Residue

释义

Quadratic Residue

If there is an Integer such that

(1)

then

is said to be a quadratic residue (mod

). If not,

is said to be a quadratic nonresidue (mod

). Forexample,

, so 6 is a quadratic residue (mod 10). The entire set of quadratic residues (mod 10) are given by1, 4, 5, 6, and 9, since

making the numbers 2, 3, 7, and 8 the quadratic nonresidues (mod 10).

A list of quadratic residues for is given below (Sloane's A046071), with those numbers not in the list being quadraticnonresidues of .

	Quadratic Residues
1	(none)
2	1
3	1
4	1
5	1, 4
6	1, 3, 4
7	1, 2, 4
8	1, 4
9	1, 4, 7
10	1, 4, 5, 6, 9
11	1, 3, 4, 5, 9
12	1, 4, 9
13	1, 3, 4, 9, 10, 12
14	1, 2, 4, 7, 8, 9, 11
15	1, 4, 6, 9, 10
16	1, 4, 9
17	1, 2, 4, 8, 9, 13, 15, 16
18	1, 4, 7, 9, 10, 13, 16
19	1, 4, 5, 6, 7, 9, 11, 16, 17
20	1, 4, 5, 9, 16

Given an Odd Prime and an Integer , then the Legendre Symbol is given by

(2)

(3)

then

is a quadratic residue (+) or nonresidue (

). This can be seen since if

is a quadratic residue of

,then there exists a square

such that

, so

(4)

and

is congruent to 1 (mod

) by Fermat's Little Theorem.

is given by

(5)

More generally, let be a quadratic residue modulo an Odd Prime . Choose such that the Legendre Symbol. Then defining

			(6)
			(7)
			(8)

gives

			(9)
			(10)

and a solution to the quadratic Congruence is

(11)

The following table gives the Primes which have a given number as a quadratic residue.

	Primes





2
3
5
6

Finding the Continued Fraction of a Square Root and usingthe relationship

(12)

for the

th Convergent

gives

(13)

Therefore,

is a quadratic residue of

. But since

is a quadratic residue, as must be

.But since

is a quadratic residue, so is

, and we see that

are all quadratic residues of

.This method is not guaranteed to produce all quadratic residues, but can often produce several small ones in the case oflarge

, enabling

to be factored.

The number of Squares in is related to the number of quadraticresidues in by

(14)

for

(Stangl 1996). Both

and

are Multiplicative Functions.

See also Euler's Criterion, Multiplicative Function,Quadratic Reciprocity Theorem, Riemann Hypothesis

References

Burton, D. M. Elementary Number Theory, 4th ed. New York: McGraw-Hill, p. 201, 1997.

Courant, R. and Robbins, H. ``Quadratic Residues.'' §2.3 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 38-40, 1996.

Guy, R. K. ``Quadratic Residues. Schur's Conjecture'' and ``Patterns of Quadratic Residues.'' §F5 and F6 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 244-248, 1994.

Niven, I. and Zuckerman, H. An Introduction to the Theory of Numbers, 4th ed. New York: Wiley, p. 84, 1980.

Rosen, K. H. Ch. 9 in Elementary Number Theory and Its Applications, 3rd ed. Reading, MA: Addison-Wesley, 1993.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 63-66, 1993.

Sloane, N. J. A. Sequence A046071in ``The On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html.

Stangl, W. D. ``Counting Squares in .'' Math. Mag. 69, 285-289, 1996.

Wagon, S. ``Quadratic Residues.'' §9.2 in Mathematica in Action. New York: W. H. Freeman, pp. 292-296, 1991.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。