Blogs, Mathematical Reasoning, MR Study Help

Direct Proof: a2=b2mod n.

We now get into actual proof writing as we begin to show that theorems must be true. For the following theorem we will be only assuming definitions and the lemma given to us. Anything else that is used will need to be proven.

Lemma

Let \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{N}\). Then, \(a \equiv b \mod n\) if and only if \(n | b-a\).

Using this lemma, prove the following.

Theorem

Let \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{N}\). If \(a \equiv b \mod n\), then \(a^{2} \equiv b^{2} \mod n\).

As we begin the process of writing the proof of the theorem, we first want to write down any information that will be useful. Such things would include:

  • The theorem and any lemma in terms of symbolic logic.
  • Definitions of any words used.
  • Anything we remember relating to the terms used.
  • A list of statements that are given.
  • A list of statements that need to be shown.

Symbolic Logic-Theorem

We begin by rewriting the theorem using symbolic logic. If you would like more help on turning sentences into symbolic logic, there is more available in the post Translating to symbolic logic and back.

For this problem, we first note that the variables we will have are \(a,b,n\). We have that the statement \(p(a,b,n)=(a \equiv b \mod n)\) and \(q(a,b,n)=a^{2} \equiv b^{2} \mod n\). These are then connected using an if then, so we have \(p(a,b,n) \rightarrow q(a,b,n)\). Since this statement is made for any \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{N}\), we can rewrite the theorem as \[\forall (a,b \in \mathbb{Z} \wedge n \in \mathbb{N}), p(a,b,n) \rightarrow q(a,b,n).\]

Now that we have this, we note that an if then is true as long as whenever the if part is true, the then part is also true. Therefore, in order to prove this theorem, we must show that, regardless of what integers \(a\) and \(b\) and natural number \(n\) we use, as long as \(a \equiv b \mod n\), we must have \(a^{2} \equiv b^{2} \mod n\).

Symbolic Logic-Lemma

Again, we will do the same process for the lemma we just did for the theorem. In this case, we have variables \(a,b \in \mathbb{Z}\) and \(n\in \mathbb{N}\). We, furthermore, have that \(p(a,b,n)=a \equiv b \mod n\) and \(q(a,b,n)=n|(b-a)\). Therefore, we get that the statement is equivalent to \[\forall (a,b \in \mathbb{Z} \cap n \in \mathbb{N}), p(a,b,n) \leftrightarrow q(a,b,n).\]

This means that \(p(a,b,n)\) if and only if \(q(a,b,n)\) is true. That is, these are equivalent statements and proving or disproving one will count as a proof or disproof of the other.

Definitions

As we read through these statements, we see multiple things that need to be defined. When we do so, we will also try to write out any thing that we may know or think is equivalent.

  • \(\mathbb{Z}\) is the set of integers.
  • \(\mathbb{N}\) is the set of natural numbers.
  • \(a | b\).
    • \(a\) divides \(b\).
    • \(b=ka\) for some integer \(k\).
  • \(a \equiv b \mod n\).
    • When \(a\) and \(b\) are divided by \(n\), the remainders are the same.
    • This is equivalent to \(n |(b-a)\) by the lemma.
    • For more on modular arithmetic, see the post Modular Arithmetic: 2+2=1!

Given and used

Now that we know what the theorem is saying, we want to list out what we are given, and what we need to show. We will also relate each of these to anything else we have, so that eventually we can move from one point to the other.

Given Must Show
\(a \equiv b \mod n\) \(a^{2} \equiv b^{2} \mod n\)
\(n | (b-a)\) \(n | b^{2}-a^{2}\)
\(b-a=nk_{1}\) (\(k_{1} \in \mathbb{Z}\)) \(b^{2}-a^{2}=nk_{2}\) (\(k_{2}\in \mathbb{Z}\))

Using the table, we see that we are given that \(a \equiv b \mod n\), which is equivalent to any of the other statements in the first column. Using these, we then need to show any of the things in the second column, because these are all equivalent to \(a^{2} \equiv b^{2} \mod n\). Now, we need to use some creativity and figure out how to get from the first column to the second column. When doing so, I try to combine both using some type of substitution. That is, start with \(b^{2}-a^{2}\) and try to rewrite this using something in the first column. Then, hopefully, we will get what we are looking for.

In this case, we see that \(b^{2}-a^{2}=(b-a)(b+a)\) because we can factor the difference of squares using the distributive property of real numbers. We can then see that \(b+a=nk_{1}\), so \((b-a)(b+a)=(b-a)nk_{1}\). This is then the product of an integer with \(n\), so the previous is divisible by \(n\). We are now ready to write out proof.

Proof

Let \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{N}\) such that \(a \equiv b \mod n\). We note, by the lemma, that this means that \(n |b-a\). Therefore, \(b-a=nk_{1}\) for some integer \(k_{1}\). Using this, we find that
\begin{align*}
b^{2}-a^{2}&=(b-a)(b+a) \\
&=nk_{1}(b+a).
\end{align*}
Now, let \(k_{2}=k_{1}(b+a)\). We note that \(k_{2}\) is the product of an integer and the sum of integers and is therefore an integer. Hence, \(b^{2}-a^{2}=nk_{2}\) for some integer \(k_{2}\). This gives use that \(n|b^{2}-a^{2}\) by definition. Therefore, \(a^{2} \equiv b^{2} \mod n\) by our lemma.

Conclusion

Here the proof itself is actually quite short compared to everything that was needed to create the proof. As we try to come up with the proof, we spend a lot of time rewriting things so that we are absolutely sure what we are given and what we are trying to say. After all of this, there will always be a point where we need to make a connection between to ideas using our own creativity. Here, we needed to factor out \(b^{2}-a^{2}\) and substitute in \(b-a=nk_{1}\) in order to get our desired result. While this happens frequently in the proofs in our introduction to proofs class, there are many other techniques used to make the connection. Make sure to continue to practice on more example so that you get used to seeing this.

I hope that you learned something about the process of writing proofs and that this will help you in your studies. For more help visit here. If you enjoyed the post or learned something, make sure to like it and share with anyone else that may need help on similar topics.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.