Problem 6 in the midterm asked to prove that if is an integer and is a multiple of , then is already a multiple of .

As we now know from lecture, the key seems to be that is a prime number. For example, it is not necessarily the case that if is a multiple of , then is a multiple of . For a counterexample, we can take .

The proof I was expecting was by contrapositive: If is not a multiple of , then it has a non-zero remainder when divided by , so or for some integer . This means that or . After some rearranging, we see that in both cases we have for some integer , but then is not a multiple of after all.

Using Euclid’s lemma, we can give another proof that is particularly short: Since is a prime, then whenever divides a product, it divides one of the factors. We are told that divides , so it divides or it divides . On the other hand, this brevity is only apparent, as the proof uses Euclid’s lemma, which makes use of the Euclidean algorithm and the possibility of writing the GCD of two numbers as a linear combination of them. When written in full detail, this argument ends up being longer than the one we gave first.

A different approach was suggested during lecture, and I think it leads to a nice argument, so I am presenting it here.

The idea was simple: Suppose that is a multiple of . Then there is an integer such that , so we can write

** If** (and it is a big if) we manage to show that , then we see that is an integer, and the displayed equation above tells us that is times an integer, so it is a multiple of .

Let’s see if we can make this idea work. We simply divide by and see what we are left with:

for some integer and some remainder with . If , we are done: is indeed a multiple of . Let’s examine what happens otherwise.

We have then that and

This means that is an integer, so . But , so . Since is a multiple of , the only possibilities are that or .

In the first case, we have that , so is a multiple of after all.

In the second case, we have . We can proceed in two ways now: A short argument goes by noticing that , so

,

and is again a multiple of . We have now proved that, no matter what the remainder is when we divide by , in any case we have that is a multiple of , and this is what we needed.

A slightly longer argument but perhaps less of a trick goes by noticing that if , then is even. One easily verifies that if is odd, then is also odd, so it must be the case that itself is even. Say, . Then , or

so is indeed a multiple of , and we are done as before.

Where do we go from here?

We are done with the argument, but it is worth continuing a bit further: We have that is a multiple of , say . Then , so the number we were calling before, is , that is, is after all a multiple of , and *is* an integer. As it turned out, we ended up not needing this in our proof, but now we now it is true anyway.

Where does this argument fail when we use a number like instead of ? Exactly the same argument would give us: If , then . We can divide by , and we get , so and . It follows that . As before, , so , so or . If , then is a multiple of . If or , then is again a multiple of . However, if , then , and all we can conclude is that is even.

This suggests a natural question: Let be a positive integer. Consider the following statement, that we will call :

Whenever is a multiple of , then in fact is a multiple of .

In the paragraph above, we saw that is false, and before we saw that is true.

Question.For which values of is true?

It is true for prime (do you see why?), but this is not necessary; for example, it is true for . If you find the general solution, let me know and you can turn it in as extra credit.