Math 160 Mathematical Problems and Games, Fall 2002
Problem Set 8: hand in one problem on Tuesday, November 12.
Instructions for this week: As always, try all of the problems. Then
choose one to write up and hand in. Either do one of the problems below,
problem 2 or 3 from last week's homework if you didn't write it up before,
or do a revision of a problem from earlier in the semester that you wanted
to work on more. If you do a revision, please remember to hand in the
original as well as the revision.
A few words about mod and divisibility: When dividing an integer
x by a positive integer n, sometimes it divides evenly (meaning
that x/n is another integer, like if x=6 and n=3), and
sometimes it doesn't (like if x=7 and n=3). In either
case, you can find a quotient q and remainder r which are integers,
such that x = qn + r, and 0 <= r < n
. (Exercise: What are the quotient and remainder when a) x
=6 and n=3, b) x=7 and n=3?) (Note: This
works fine when x is negative; what would you have to modify if
n were negative?) The phrase "x mod n" means the
remainder when x is divided by n. (Exercise: Show
that if a mod n = b mod n, then the difference
between a and b is a multiple of n.)
1. a) Prove that for any three-digit number ABC, ABC mod 3 = A +
B + C mod 3. b) Prove that any number (of any length) is evenly
divisible by 3 if and only if the sum of its digits is divisible by 3. c)
Prove that any number is evenly divisible by 9 if and only if the sum of
its digits is divisible by 9. (Note: Instead of writing ABC,
you can write a number of arbitrary length as AkAk-1
Ak-2 ... A2A1A0.)
2. Prove that for any positive integer n, n3
+ 2n is divisible by 3.
3. Prove that if p is a prime number greater than 3, then
p2 - 1 is divisible by 24.
If any of this is confusing or you want a hint,
email me at ksir@math.sunysb.edu
.