Math 312 Worksheet - University Of British Columbia -2016 Page 6
ADVERTISEMENT
1
2
3
4
5
6
7
86
PROBLEM 5 (15 points)
(a) (2pts) Explain what it means for an integer n > 0 to be a
pseudoprime to the base b
.
Z
2
Answer: An integer n > 0 is a pseudoprime to base b
if it
Z
2
fools Fermat’s test in base b. That is, if n is composite and satisfies
n 1
b
1 (mod n).
(b) (9pts) Prove that 1729 = 7 13 19 is a Carmichael number.
Answer: Let n = 1729. The integer n is a Carmichael number if
n 1
b
1 (mod n)
for all bases b such that (n, b) = 1.
By the CRT it suffices to show that for any b
such that (b, n) = 1
Z
2
we have
n 1
n 1
n 1
(i) b
1 (mod 7),
(ii) b
1 (mod 13),
(iii) b
1 (mod 19).
By Fermat’s Little Theorem we have
6
12
18
(a) b
1 (mod 7),
(b) b
1 (mod 13),
(c) b
1 (mod 19).
Note that n
1 = 1728 is divisible by 4 (the last 2 digits are 28 which
is divisible by 4) and by 9 (the sum of its digits is 18). Thus n
1 is
also divisible by 6, 12 and 18. Now (i), (ii) and (iii) follow from (a),
(b) and (c), respectively.
(c) (4pts) Show, without using the explicit factorization of 1729,
but using the following congruences instead, that 1729 is composite
18
36
2
1065 (mod 1729)
and 2
1 (mod 1729).
18
2
36
Answer: Let x = 2
. We have x
= 2
1 (mod 1729), hence
if 1729 is a prime we also have x
1 (mod 1729). This means
18
x = 2
1065
1 (mod 1729) which is impossible. We conclude
that 1729 is composite.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education