Page 295 - Discrete Mathematics and Its Applications

274 4 / Number Theory and Cryptography

50. Show that if a, b, and m are integers such that m ≥ 2 and of the form 4k + 3, where k is a nonnegative inte-
a ≡ b(mod m), then gcd(a, m) = gcd(b, m). ger. [Hint: Suppose that there are only finitely many
2
∗ 51. Prove or disprove that n − 79n + 1601 is prime when- such primes q 1 ,q 2 ,...,q n , and consider the number
ever n is a positive integer. 4q 1 q 2 ··· q n − 1.]
52. Prove or disprove that p 1 p 2 ··· p n + 1 is prime for every ∗ 56. Prove that the set of positive rational numbers is countable
positive integer n, where p 1 ,p 2 ,...,p n are the n small- by setting up a function that assigns to a rational num-
est prime numbers. ber p/q with gcd(p, q) = 1 the base 11 number formed
53. Show that there is a composite integer in every arithmetic by the decimal representation of p followed by the base
progression ak + b, k = 1, 2,... where a and b are pos- 11 digit A, which corresponds to the decimal number 10,
itive integers. followed by the decimal representation of q.
54. Adapt the proof in the text that there are infinitely many
∗ 57. Prove that the set of positive rational numbers is countable
primes to prove that there are infinitely many primes
of the form 3k + 2, where k is a nonnegative inte- by showing that the function K is a one-to-one correspon-
ger. [Hint: Suppose that there are only finitely many dence between the set of positive rational numbers and
2a 1 2a 2
such primes q 1 ,q 2 ,...,q n , and consider the number the set of positive integers if K(m/n) = p 1 p 2 · ··· ·
2b 1 −1 2b 2 −1 2b t −1
2a s
3q 1 q 2 ··· q n − 1.] p q q · ··· · q , where gcd(m, n) = 1
s 1 2 t
55. Adapt the proof in the text that there are infinitely many and the prime-power factorizations of m and n are m =
a 1 a 2
b t
b 1 b 2
primes to prove that there are infinitely many primes p p · ··· · p a s and n = q q ··· q .
1 2 s 1 2 t

4.4 Solving Congruences

Introduction

Solving linear congruences, which have the form ax ≡ b (mod m), is an essential task in the
study of number theory and its applications, just as solving linear equations plays an important
role in calculus and linear algebra. To solve linear congruences, we employ inverses modulo m.
We explain how to work backwards through the steps of the Euclidean algorithm to find inverses
modulo m. Once we have found an inverse of a modulo m, we solve the congruence ax ≡ b
(mod m) by multiplying both sides of the congruence by this inverse.
Simultaneous systems of linear congruence have been studied since ancient times. For
example, the Chinese mathematician Sun-Tsu studied them in the first century. We will show
how to solve systems of linear congruences modulo pairwise relatively prime moduli. The result
we will prove is called the Chinese remainder theorem, and our proof will give a method to
find all solutions of such systems of congruences. We will also show how to use the Chinese
remainder theorem as a basis for performing arithmetic with large integers.
We will introduce a useful result of Fermat, known as Fermat’s little theorem, which states
that if p is prime and p does not divide a, then a p−1 ≡ 1 (mod p).We will examine the converse
ofthisstatement,whichwillleadustotheconceptofapseudoprime.Apseudoprimemtothebase
a is a composite integer m that masquerades as a prime by satisfying the congruence a m−1 ≡ 1
(mod m). We will also give an example of a Carmichael number, which is a composite integer
that is a pseudoprime to all bases a relatively prime to it.
We also introduce the notion of discrete logarithms, which are analogous to ordinary loga-
rithms. To define discrete logarithms we must first define primitive roots. A primitive root of a
prime p is an integer r such that every integer not divisible by p is congruent to a power of r
e
modulo p.If r is a primitive root of p and r ≡ a(mod p), then e is the discrete logarithm of a
modulo p to the base r. Finding discrete logarithms turns out to be an extremely difficult prob-
lem in general. The difficulty of this problem is the basis for the security of many cryptographic
systems.