From Wikipedia, the free encyclopedia
Quadratic Residues
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25
|
| n2
|
1
|
4
|
9
|
16
|
25
|
36
|
49
|
64
|
81
|
100 |
121 |
144 |
169 |
196 |
225 |
256 |
289 |
324 |
361 |
400 |
441 |
484 |
529 |
576 |
625
|
| mod 2
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1
|
| mod 3
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1 |
1 |
0
|
1
|
| mod 4
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1 |
0
|
1
|
| mod 5
|
1 |
4 |
4 |
1 |
0
|
1 |
4 |
4 |
1 |
0
|
1 |
4 |
4 |
1 |
0
|
1 |
4 |
4 |
1 |
0
|
1 |
4 |
4 |
1 |
0
|
| mod 6
|
1 |
4 |
3 |
4 |
1 |
0
|
1 |
4 |
3 |
4 |
1 |
0
|
1 |
4 |
3 |
4 |
1 |
0
|
1 |
4 |
3 |
4 |
1 |
0
|
1
|
| mod 7
|
1 |
4 |
2 |
2 |
4 |
1 |
0
|
1 |
4 |
2 |
2 |
4 |
1 |
0
|
1 |
4 |
2 |
2 |
4 |
1 |
0
|
1 |
4 |
2 |
2
|
| mod 8
|
1 |
4 |
1 |
0
|
1 |
4 |
1 |
0
|
1 |
4 |
1 |
0
|
1 |
4 |
1 |
0
|
1 |
4 |
1 |
0
|
1 |
4 |
1 |
0
|
1
|
| mod 9
|
1 |
4 |
0 |
7 |
7 |
0 |
4 |
1 |
0
|
1 |
4 |
0 |
7 |
7 |
0 |
4 |
1 |
0
|
1 |
4 |
0 |
7 |
7 |
0 |
4
|
| mod 10
|
1 |
4 |
9 |
6 |
5 |
6 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
6 |
5 |
6 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
6 |
5
|
| mod 11
|
1 |
4 |
9 |
5 |
3 |
3 |
5 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
5 |
3 |
3 |
5 |
9 |
4 |
1 |
0
|
1 |
4 |
9
|
| mod 12
|
1 |
4 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
4 |
1 |
0
|
1
|
| mod 13
|
1 |
4 |
9 |
3 |
12 |
10 |
10 |
12 |
3 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
3 |
12 |
10 |
10 |
12 |
3 |
9 |
4 |
1
|
| mod 14
|
1 |
4 |
9 |
2 |
11 |
8 |
7 |
8 |
11 |
2 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
2 |
11 |
8 |
7 |
8 |
11 |
2 |
9
|
| mod 15
|
1 |
4 |
9 |
1 |
10 |
6 |
4 |
4 |
6 |
10 |
1 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
1 |
10 |
6 |
4 |
4 |
6 |
10
|
| mod 16
|
1 |
4 |
9 |
0 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
0 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
0 |
9 |
4 |
1 |
0
|
1
|
| mod 17
|
1 |
4 |
9 |
16 |
8 |
2 |
15 |
13 |
13 |
15 |
2 |
8 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
8 |
2 |
15 |
13
|
| mod 18
|
1 |
4 |
9 |
16 |
7 |
0 |
13 |
10 |
9 |
10 |
13 |
0 |
7 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
7 |
0 |
13
|
| mod 19
|
1 |
4 |
9 |
16 |
6 |
17 |
11 |
7 |
5 |
5 |
7 |
11 |
17 |
6 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
6 |
17
|
| mod 20
|
1 |
4 |
9 |
16 |
5 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
5 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
5
|
| mod 21
|
1 |
4 |
9 |
16 |
4 |
15 |
7 |
1 |
18 |
16 |
16 |
18 |
1 |
7 |
15 |
4 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16
|
| mod 22
|
1 |
4 |
9 |
16 |
3 |
14 |
5 |
20 |
15 |
12 |
11 |
12 |
15 |
20 |
5 |
14 |
3 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9
|
| mod 23
|
1 |
4 |
9 |
16 |
2 |
13 |
3 |
18 |
12 |
8 |
6 |
6 |
8 |
12 |
18 |
3 |
13 |
2 |
16 |
9 |
4 |
1 |
0
|
1 |
4
|
| mod 24
|
1 |
4 |
9 |
16 |
1 |
12 |
1 |
16 |
9 |
4 |
1 |
0
|
1 |
4 |
9 |
16 |
1 |
12 |
1 |
16 |
9 |
4 |
1 |
0
|
1
|
| mod 25
|
1 |
4 |
9 |
16 |
0 |
11 |
24 |
14 |
6 |
0 |
21 |
19 |
19 |
21 |
0 |
6 |
14 |
24 |
11 |
0 |
16 |
9 |
4 |
1 |
0
|
