Question 2:
2 | (a) | (i) | 59
191
309
441
559
691
809
941
No need to state program example given on the
right | B1
[1] | 2.5 | for i in range(0,1000):
if i*i%1000==481:
print(i)
Need all the values for the mark
(ii) | 481 is a quadratic residue modulo 1000
because there is an integer x such that
x2 481 (mod 1000) . For example x = 59. | B1
[1] | 2.4 | Need an actual example or reference
to working in 2(a)(i) to get this
mark.
(iii) | Quadratic residues modulo 11 are
112 (mod 11)
422 (mod 11)
932 (mod 11)
542 (mod 11)
352 (mod 11)
(squaring 6, 7, 8, 9, 10 give values already in
this list) | M1
A1
[2] | 2.5
1.2 | Accept appropriate code instead,
must be stated
SC1 for 1, 3, 4, 5 and 9.
(iv) | Quadratic residues modulo 13 are
112 (mod 13)
422 (mod 13)
932 (mod 13)
342 (mod 13)
1252 (mod 13)
1062 (mod 13)
(squaring 7, 8, 9, 10, 11, 12 give values already
in this list) | M1
A1
[2] | 2.5
1.2 | Accept appropriate code instead
SC1 for 1, 3, 4, 9, 10 and 12.
(v) | ( n − m ) 2 = n 2 − 2 m n + m 2 ( = m 2 + n ( n − 2 m ) )
So (n−m)2 and m 2 differ by a multiple of
n. Therefore m 2  ( n − m ) 2 ( m o d n ) | M1
A1
[2] | 1.1a
2.1 | Multiplying out the brackets
Explanation or see n(n – 2m), and
consideration modulo n. | Allow e.g. 𝑛2−2𝑚𝑛+
𝑚2 = 0±0 + 𝑚2 (mod 𝑛)
(vi) | By part (v)
m 2  ( p − m ) 2 m o d p
2 1  ( p − 1 ) 2 m o d p
2 2  ( p − 2 ) 2 m o d p
...
 p −  1 2  p + 1 2 
   m o d p
2 2
Therefore the number of quadratic residues mod
p − 1
p is at most .
2
p − 1
Suppose n, m are such that 1  m  n 
2
and that m 2 = n 2 m o d p . Then p divides
n2 – m2 = (n – m)(n + m) and so p divides either
n – m or n + m (since p is prime).
But 0n−mn+m pand so n – m = 0
Therefore m = n.
Therefore each distinct integer between 1 and
p − 1
has a distinct square mod p and so there
2
p−1
are quadratic residues mod p.
2 | M1
A1
M1
A1
[4] | 3.1a
2.1
3.1a
2.1 | Use of previous result with n
replaced by p.
Explanation that pairing up p – 1
p − 1
values gives pairs.
2 | m may be replaced by a
specific value.
(b) | (i) | If 91 were prime then 2 9 0  1 m o d 9 1 by
Fermat’s little theorem.
However 2 9 0  6 4 m o d 9 1 | M1
A1
[2] | 2.2a
3.2a | soi. Need to see idea that 290 – 1 is
not a multiple of 91 implies 91 is not
prime. | Can use values of a other
than 2 here.
(ii) | 561 by the program on the right
Appropriate structure program
Loops with correct range dependent on m, n.
Check for common divisors and divisors with if
statement (and tracking greatest one found in
case of coprime function)
Fully correct program. | M1
M1
M1
M1
M1
A1
[6] | 3.3
3.3
3.4
2.1
2.1
2.3 | Pseudo code accepted, condone
lack of syntax, give reasonable
BOD on possible transcription
errors
def isprime(n):
prime=1
for i in range(2,n):
if n%i==0:
prime=0
return prime
def coprime(m,n):
coprime=1
for i in range(2,m+1):
if n%i==0 and m%i==0:
coprime=i
return coprime
for i in range(500,600):
candidate = 1
if isprime(i)==1:
candidate = 0
if isprime(i)==0:
for j in range(1,i):
if coprime(j,i)==1 and
((j**(i-1))%i)!=1:
candidate = 0
if candidate == 1:
print(i) | M1 for prime test
M1 for coprime test
M1 for test over range (can
be implied by any stated
output in this range).
M1 for rejecting primes
M1 for testing equation for
appropriate values.
A1 for value 561.