- Answers to Exercises 265
on his or her birthday is 1/ 3653 =1/ 48 , 627 ,125. Let’s say there are 2 billion
married people; then we can expect that 2, 000 , 000 , 000 / 48 , 627 , 125 ≈41 of
them have the same birthday as their mother, father, and spouse.
6 Integers, Divisors, and Primes
6.1 Divisibility of Integers
6.1.1. a=a·1=(−a)·(−1).
6.1.2. (a) even; (b) odd; (c)a=0.
6.1.3. (a) Ifb=amandc=bn, thenc=amn. (b) Ifb=amandc=an,
thenb+c=a(m+n) andb−c=a(m−n). (c) Ifb=amanda, b >0,
thenm>0; hencem≥1, and sob≥a. (d) Trivial ifa= 0. Assumea =0.
Ifb=amanda=bn, thena=amn,somn= 1. Hence eitherm=n=1
orm=n=−1.
6.1.4. We havea=cnandb=cm, hencer=b−aq=c(m−nq).
6.1.5. We haveb=am,c=aq+randc=bt+s. Hences=c−bt=
(aq+r)−(am)t=(q−mt)a+r. Since 0≤r<a, the remainder of the
divisions÷aisr.
6.1.6. (a)a^2 −1=(a−1)(a+ 1). (b)an−1=(a−1)(an−^1 +···+a+ 1).
6.3 Factorization into Primes
6.3.1. There is a smallest one amongpositivecriminals (indeed, in every
set of positive integers), but a set of negative integers need not have a
smallest element (if it is infinite).
6.3.2. Yes, the number 2.
6.3.3. (a)poccurs in the prime factorization ofab, so it must occur in
the prime factorization ofaor in the prime factorization ofb.
(b)p|a(b/a), butpa, so by (a), we must havep|(b/a).
6.3.4. Letn=p 1 p 2 ···pk; eachpi≥2; hencen≥ 2 k.
6.3.5. Ifri=rj, thenia−jais divisible byp. Butia−ja=(i−j)aand
neitheranori−jis divisible byp. Hence theriare all different. None of
them is 0. Their number isp−1, so every value 1, 2 ,...,p−1 must occur
among theri.
6.3.6. For a primep, the proof is the same as for 2. Ifnis composite but
not a square, then there is a primepthat occurs in the prime factorization
ofnan odd number of times. We can repeat the proof by looking at thisp.
6.3.7. Fact: If k
√
nis not an integer, then it is irrational. Proof: There is a
prime that occurs in the prime factorization ofn,sayttimes, wherekt.If