Let be integers with divisible by . Prove that is divisible by .
Solution
We need to prove that is divisible by and by . We will give proofs by contradiction.
Suppose odd. This implies that , and are odd. Therefore, is odd and certainly not divisible by . This contradiction shows that is even.
Suppose that is not divisible by . Then , and are not divisible by , i.e. they are in (possibly distinct) congruence classes among the following congruence classes mod .
We conclude that is equal to , , or . Therefore, is not divisible by and consequently not by . This contradiction shows that is divisible by .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.