6.042/18.062J Mathematics for Computer Science February 22,2005
Srini Devadas and Eric Lehman
Problem Set 4 Solutions
Due,Monday,February 28 at 9 PM
Problem 1,Prove all of the following statements except for the two that are false; for
those,provide counterexamples,Assume n > 1,When proving each statement,you may
assume all its predecessors,
(a) a ≡ a (mod n)
Solution,Every number divides zero,so n (a? a),which means a ≡ a (mod n).|
(b) a ≡ b (mod n) implies b ≡ a (mod n)
Solution,The statement a ≡ b (mod n) implies n (a? b),which means there is an
integer k such that nk = a? b,Thus,n(?k) = b? a
|
,so n (b? a) as well,This means |
b ≡ a (mod n),
(c) a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c (mod n)
Solution,The two assumptions imply n (a? b) and n (b? c),Thus,n divides the | |
linear combination (a? b) + (b? c) = a? c as well,This means n (a? c).|
(d) a ≡ b (mod n) implies a + c ≡ b + c (mod n)
Solution,The?rst statement implies n | (a? b),Rewriting the right side gives
n (a + c)? (b + c),which means a + c ≡ b + c (mod n).|
(e) a ≡ b (mod n) implies ac ≡ bc (mod n)
Solution,The?rst statement implies n (a?b),Thus,n also divides c(a?b) = ac?bc,
Therefore,ac ≡ bc (mod n),
|
(f) ac ≡ bc (mod n) implies a ≡ b (mod n) provided c?≡ 0 (mod n),
Solution,This is false,For example,6 2 ≡ 8 · 2 (mod 4),but 6?≡ 8 (mod 4).·
(g) a ≡ b (mod n) and c ≡ d (mod n) imply a + c ≡ b + d (mod n)
Solution,The assumptions,together with part (e),give:
a + c ≡ b + c (mod n)
b + c ≡ b + d (mod n)
Now part (c) implies a + c ≡ b + d (mod n),
2 Problem Set 4
(h) a ≡ b (mod n) and c ≡ d (mod n) imply ac ≡ bd (mod n)
Solution,The assumptions,together with part (e),give:
ac ≡ bc (mod n)
bc ≡ bd (mod n)
Now part (c) implies ac ≡ bc (mod n).
(i) a ≡ b (mod n) implies a
k
≡ b
k
(mod n) for all k ≥ 0,
Solution,We use induction,Suppose that a ≡ b (mod n),Let P(k) be the proposi-
k
tion that a ≡ b
k
,
0
Base case,P(0) is true,since a = b
0
= 1 and 1 ≡ 1 (mod n) by part (a),
k
Inductive step,For k ≥ 0,we assume P(k) to prove P(k + 1),Thus,assume a ≡ b
k
(mod n),Combining this assmption and the fact that a ≡ b (mod n) using part (g),
k+1
≡ b
k+1
we get a (mod n).
By induction,P(k) holds for all k ≥ 0.
(j) a ≡ b (mod n) implies k
a
≡ k
b
(mod n) for all k ≥ 0.
Solution,This is false,For example,0 ≡ 3 (mod 3),but 2
0
≡ 2
3
(mod 3).
(k) (a rem n) ≡ a (mod n)
Solution,By de?nition of rem,a rem n = a? qn for some integer q,So we can
reason as follows,
(a rem n) ≡ a? qn (mod n)
≡ a (mod n) from (d) and qn ≡ 0 (mod n)
Problem 2,Prove that there exists an integer k
1
such that
k k
1
≡ 1 (mod n)·
provided gcd(k,n) = 1,Assume n > 1,
Solution,If gcd(k,n) = 1,then there exist integers x and y such that kx + yn = 1,
Therefore,yn = 1? kx,which means n (1? kx) and so kx ≡ 1 (mod n),Let k
1
be x.|
Problem 3,Reviewing the analysis of RSA may help you solve the following problems,
You may assume results proved in recitation,
(a) Let n be a nonnegative integer,Prove that n and n
5
have the same last digit,For
example,
2
5
= 32 79
5
= 3077056399
Solution,The correctness of RSA relies on the following fact,if p and q are distinct
primes,then
m
1+k(p?1)(q?1)
≡ m (mod pq)
for all m and k,Setting k = 1,p = 5,and q = 2 proves the claim.
3 Problem Set 4
(b) Suppose that p
1
,...,p
k
are distinct primes,Prove that
m
1+(p
1
1)(p
2
1)···(p
k
1)
≡ m (mod p
1
p
2
···p
k
)
for all m and all k ≥ 1.
Solution,If m is a multiple of a prime p
j
,then
m
1+(p
1
1)(p
2
1)···(p
k
1)
≡ m (mod p
j
) (*)
holds,because both sides are congruent to 0,If m is not a multiple of p
j
,then con-
gruence (*) still holds because,
m
1+(p
1
1)(p
2
1)···(p
k
1)
≡ m·(m
p
j
1
)
(p
1
1)(p
2
1)···(p
k
1)/(p
j
1)
(mod p
j
)
(mod p
j
)≡ m·1
(p
1
1)(p
2
1)···(p
k
1)/(p
j
1)
(mod p
j
)≡ m
The second step uses Fermat’s Theorem,Now the congruence (*) means that,
m
1+(p
1
1)(p
2
1)···(p
k
1)
mp
j
|
Thus,p
j
appears in the prime factorization of right side,Since this argument is valid
for every prime p
j
where 1 ≤ j ≤ k,all of the primes p
1
,...,p
k
appear in the prime
factorization of,
1+(p
1
1)(p
2
1)···(p
k
1)
mm
Therefore,
p
1
p
2
m
1+(p
1
1)(p
2
1)···(p
k
1)
m···p
k
|
Rewriting this as a congruence gives,
m
1+(p
1
1)(p
2
1)···(p
k
1)
≡ m (mod p
1
p
2
···p
k
)
Problem 4,Suppose that p is a prime,
(a) An integer k is self-inverse if k·k ≡ 1 (mod p),Find all integers that are self-inverse
mod p,
Solution,The congruence holds if and only if p k
2
1 which is equivalent to
p (k + 1)(k? 1),this holds if and only if either p
|
k + 1 or p k? 1,Thus,k ≡ ±1| | |
(mod p),
(b) Wilson’s Theorem says that (p?1)! ≡?1 (mod p),The English mathematician Ed-
ward Waring said that this statement would probably be extremely dif?cult to prove
because no one had even devised an adequate notation for dealing with primes,
(Gauss proved it while standing.) Your turn! Stand up,if you like,and try can-
celling terms of (p?1)! in pairs,
Solution,If p = 2,then the theorem holds,because 1! ≡?1 (mod 2),If p > 2,
then p? 1 and 1 are distinct terms in the product 1 2 ····(p? 1),and these are the ·
4 Problem Set 4
only self-inverses,Consequently,we can pair each of the remaining terms with its
multiplicative inverse,Since the product of a number and its inverse is congruent
to 1,all of these remaining terms cancel,Therefore,we have,
(p?1)! (p?1) (mod p)≡ 1 ·
1 (mod p)≡?