# Number Theory: Problem 3

### Model Solution

Let a, b, c, p, q be integers, where p and q are positive. Suppose that $$a \equiv b \pmod{p}$$ and $$c \equiv b \pmod{q}$$ and $$q \mid p$$. By the given definition of congruence, a = b+pr and c = b + qt, where r and t are integers. Since $$q\mid p$$, we know that p = qu, where u is an integer.

Therefore, by substituting b+pr for a and b+qt for c, we get

    a - 2c = b + pr - 2(b + qt)


By substituting qu for p, we get:

    a - 2c = b + qur - 2(b + qt)
= b + qur -2b -2qt
= (-b) + q(ur - 2t)
= (-b) + qw


where w = ur - 2t.

By closure, w must be an integer. Therefore, by the definition given for congruence, $$a -2c \equiv (-b) \pmod{q}$$.

In mathematics, "closure" is a property of operations such as addition. It means that their outputs are of the same type as their inputs. For example, "the integers are closed under addition" means that if you add two integers, the result is an integer. So "by closure" is shorthand for "because the inputs are all integers and we're only using safe operations like addition and multiplication."

### Self-check

Start of proof: did you declare your variables? Did you explicitly state the given information from the hypothesis of the claim?

End of proof: did you end at the conclusion of the claim?

Specifying type information: did you declare r, t, u to be integers when you first introduced them?

Is the amount of mathematical detail in the middle of your proof similar to what's in this example? You don't have to justify every step of familiar high school algebra, but the reader should be able to verify each step without having to think too hard.

### Buggy proof 1

Now have a look at this buggy proof.

Let a, b, c, p, q be integers, where p and q are positive. Suppose that $$a \equiv b \pmod{p}$$ and $$c \equiv b \pmod{q}$$ and $$q \mid p$$. By the given definition of congruence, a = b+pr and c = b + qt, where r and t are integers. Since $$q\mid p$$, we know that p = qu, where u is an integer.

By the definition of congruence $$a -2c \equiv (-b) \pmod{q}$$ can be rewritten as a-2c=(-b) + qw, where w is an integer.

By substituting a=b+pr, c=b+qt, p=uw, we get

   a - 2c                =   (-b) + qw
b + pr - 2(b + qt)    =   (-b) + qw
b + qur - 2(b + qt)   =   (-b) + qw
(-b) + qur - 2qt      =   (-b) + qw
qur - 2qt             =   qw
ur - 2t               =   w


Both sides of this last equation are integers, so our conclusion is proved.

The big problem with this proof is that the reasoning is backwards. The second paragraph assumes that $$a -2c \equiv (-b) \pmod{q}$$ is true. But this is the conclusion we need to reach at the end of the proof, not part of our given information.

You might write backwards algebra like this on your scratch paper. This can help you gain an understanding of the problem and what the key steps in the proof might look like. However, in your final draft, this kind of work needs to be rewritten into logical order: start from the hypotheses and move fowards to the conclusion.

### Buggy Proof 2

Now, look at this buggy proof:

Let a, b, c, p, q be integers, where p and q are positive. Suppose that $$a \equiv b \pmod{p}$$ and $$c \equiv b \pmod{q}$$ and $$q \mid p$$. By the definition of congruence, a -b = pr and c-b = qt, where r and t are integers. Since $$q\mid p$$, we know that p = qu, where u is an integer.

So then 2c-2b = 2qt. So then (a-b)+(2c-2b)=pr -2qt. So $$(a-2c) +b = pr -2qt = qur -2qt = q(ur-2t)$$

Now, let w = ur - 2t. w is an integer because u, r, and t are all integers. We then have (a-2c) +b = qw\$. So, by the defintion of congruence, we have $$a -2c \equiv (-b) \pmod{q}$$, which is what we needed to show.

This one is almost ok. However, notice that it's not using the definition of congruence given in the problem statement. The problem statement said

$$x \equiv y \pmod{m}$$ if there is an integer k such that x = y + km.

And this author is using the definition:

$$x \equiv y \pmod{m}$$ if there is an integer k such that x - y = km.

Either definition is ok in the abstract, but the problem told us which one to use. More generally, it's important that authors and readers agree about which definitions they are using.