- Answers to Exercises 269
6.7.4.(a) Takea= 2 andb= 5. (b) Ifac≡bc(modmc), thenmc|ac−bc,
so there is an integerksuch thatac−bc=kmc. Sincec = 0, this implies
thata−b=km, and soa≡b (modm).
6.7.5. First, fromx≡y (modp) it follows (by the multiplication rule)
thatxv≡yv (modp), so it suffices to prove that
xu≡xv (modp). (16.1)Ifx≡0 (modp), then both sides of (16.1) are divisible byp, and the
assertion follows. Suppose thatx
≡0 (modp). Suppose that (say)u<v.
We know thatp− 1 |v−u, so we can writev−u= k(p−1) with
some positive integerk. Now we know by Fermat’s Little Theorem that
xp−^1 ≡1 (modp), hence by the multiplication rule of congruences, we
havexk(p−1)≡1 (modp), and by the multiplication rule again, we get
xv=xu·xk(p−1)≡xu (modp), which proves (16.1).
6.8 Strange Numbers
6.8.1. Tu; Sa; Th; We.
6.8.2. not-A=1⊕A;A-or-B=A⊕B⊕A·B;A-and-B=A·B.
6.8.3. 2 · 0 ≡ 2 ·3 (mod 6) but 0
≡3 (mod 6). More generally, if
m=ab(a, b >1) is a composite modulus, thena· 0 ≡a·b (modm), but
0
≡b (modm).
6.8.4. We start with the Euclidean Algorithm:
gcd(53,234527) = gcd(53,2) = gcd(1,2) = 1.Here we got 2 as 2 = 234527− 4425 ·53, and then 1 as
1=53− 26 ·2=53−26(234527− 4425 ·53) = 115051· 53 − 26 · 234527.It follows that 1≡ 115051 ·53 (mod 234527), and so 1 /53 =115051.
6.8.5. x≡ 5 ,y≡8 (mod 11).
6.8.6.(a) We have 11|x^2 − 2 x=x(x−2); hence either 11|xor 11|x−2,
sox≡0 (mod 11) andx≡2 (mod 11) are the two solutions. (b) Similarly
from 23|x^2 −4=(x−2)(x+2) we getx≡2 (mod 23) orx≡−2 (mod 23).
6.9 Number Theory and Combinatorics
6.9.1. There are two neighboring integerskandk+ 1 among the givenn
numbers (Pigeonhole Principle) that are relatively prime.
6.9.2. By the rules of inclusion-exclusion, we have to subtract fromnthe
number of multiples ofpi(between 1 andn) for everypi; then we have to