5 Congruences 117Any Carmichael numbernmust be odd, since it has an odd prime factorpsuch that
p−1dividesn−1. Furthermore a Carmichael number must have more than two prime
factors. For assumen=pq,where1<p<q<nandq−1dividesn−1. Since
q≡1mod(q− 1 ), it follows that
0 ≡pq− 1 ≡p−1mod(q− 1 ),which contradictsp<q.
The composite integer 561= 3 × 11 ×17 is a Carmichael number, since 560 is
divisible by 2,10 and 16, and it is in fact the smallest Carmichael number. The taxi-
cab number 1729, which Hardy reckoned to Ramanujan was uninteresting, is also a
Carmichael number, since 1729= 7 × 13 ×19. Indeed it is not difficult to show that
ifp,2p−1and3p−2 are all primes, withp>3, then their product is a Carmichael
number. Recently Alford, Granville and Pomerance (1994) confirmed a long-standing
conjecture by proving that there are infinitely many Carmichael numbers.
Our next topic is of greater importance. Many arithmetical problems require for
their solution the determination of an integer which is congruent to several given
integers according to various given moduli. Weconsider first a simple, but important,
special case.
Proposition 36Let m=m′m′′,wherem′and m′′are relatively prime integers. Then,
for any integers a′,a′′, there exists an integer a, which is uniquely determinedmodm,
such that
a≡a′modm′, a≡a′′modm′′.Moreover, a is relatively prime to m if and only if a′is relatively prime to m′and a′′is
relatively prime to m′′.
Proof By Proposition 22, there exist integersc′,c′′such that
c′m′′≡1modm′, c′′m′≡1modm′′.Thuse′ :=c′m′′is congruent to 1 modm′and congruent to 0 modm′′. Similarly
e′′ :=c′′m′is congruent to 0 modm′and congruent to 1 modm′′. It follows that
a=a′e′+a′′e′′is congruent toa′modm′and congruent toa′′modm′′.
It is evident that ifb≡amodm,thenalsob≡a′modm′andb≡a′′modm′′.
Conversely, ifbsatisfies these two congruences, thenb−a≡0modm′andb−a≡
0modm′′. Henceb−a≡0modm, by Proposition 3(i).
Sincem′ andm′′are relatively prime, it follows from Proposition 3(iv) that
(a,m)=1 if and only if(a,m′)=(a,m′′) =1. Sincea ≡a′modm′implies
(a,m′)=(a′,m′),anda≡a′′modm′′implies(a,m′′)=(a′′,m′′), this proves the
last statement of the proposition.
In algebraic terms, Proposition 36 says that ifm=m′m′′,wherem′andm′′are rel-
atively prime integers, then the ringZ(m)is (isomorphic to) the direct sum of the rings
Z(m′)andZ(m′′). Furthermore, the groupZ×(m)is (isomorphic to) the direct product of
the groupsZ×(m′)andZ×(m′′).