Expanded Algorithm Involving Quadratic Residues (Part Ic)

An integer r is called a quadratic residue modulo p if it is congruent to a perfect square modulo p:

x² ≡ r (mod p)

with the number of residues for a given prime given by the equation (p − 1)/2 where the one value x² = 0 is removed before division by 2.

This page, however, will deal with only composite p.

x and r values of p=15 and p=13

The expanded method can be used to determine all the x and r values belonging to a composite or prime number as shown in Tables I and II for p = 15 and p = 13, respectively. Columns 3 and 4 correspond to the calculated x values and column 5 to the calculated r ones. Note that the first r values of 4 (Table I) and 10 (Table II) correspond to (p-1)/2. Tables reproduced from the JS program used in Part Ia for x=1 and r=1.

Table I (p=15, starting with r=1)
1(15)	(a,b)	1+a	1−b	r
1(0+15)	(0,15)	1	−14	1
1(1+14)	(1,14)	2	−13	4
1(2+13)	(2,13)	3	−12	9
1(3+12)	(3,12)	4	−11	1
1(4+11)	(4,11)	5	−10	10
1(5+10)	(5,10)	6	−9	6
1(6+9)	(6,9)	7	−8	4
1(7+8)	(7,8)	8	−7	4
7(8+7)	(8,7)	9	−6	6
1(9+6)	(9,6)	10	−5	10
1(10+5)	(10,5)	11	−4	1
1(11+4)	(11,4)	12	−3	9
1(12+3)	(12,3)	13	2	4
1(13+2)	(13,2)	14	−1	1
1(14+1)	(14,1)	15	0	0
1(15+0)	(15,0)	16	1	1

Table II (p=13, starting with r=1)
1(13)	(a,b)	1+a	1−b	r
1(0+13)	(0,13)	1	−11	1
1(1+12)	(1,12)	2	−12	4
1(2+11)	(2,11)	3	−10	9
1(3+10)	(3,10)	4	−9	3
1(4+9)	(4,9)	5	−8	12
1(5+8)	(5,8)	6	−7	10
1(6+7)	(6,7)	7	−6	10
1(7+6)	(7,6)	8	−5	12
7(8+5)	(8,5)	9	−4	3
1(9+4)	(9,4)	10	−3	9
1(10+3)	(10,3)	11	−2	4
1(11+2)	(11,2)	12	−1	1
1(12+1)	(12,1)	13	0	0
1(13+0)	(13,0)	14	−1	1

Go back to Part Ib. Go to homepage.