Question

Prove the following statements with contrapositive proof. (In each case, think about how a direct proof would work. In most cases contrapositive is easier.) Suppose \(n \in Z\). If \(3 \nmid n^{2}\), then \(3 \nmid n\).

Short answer

The original statement: If \(3 \nmid n^{2}\), then \(3 \nmid n\), is proven to be true by proving its contrapositive: If \(3 | n\), then \(3 | n^{2}\). This was done by showing that if \(n\) is divisible by 3, then \(n^{2}\) is also divisible by 3.

Step-by-step solution

Formulate the contrapositive statement

The initial statement is: Suppose \(n \in Z\). If \(3 \nmid n^{2}\), then \(3 \nmid n\). The contrapositive of this would then be: If \(3 | n\) then \(3 | n^{2}\).

Prove the contrapositive statement

We know that if \(n\) is divisible by 3, then we can write: \(n=3k\) for some \(k \in Z\). Let's replace \(n\) in \(n^{2}\) with \(3k\), this gives us: \((3k)^{2} = 9k^{2}\). It is clear that \(9k^{2}\) is divisible by 3, since \(9k^{2} = 3(3k^{2})\). Therefore \(\(3 | n^{2}\)\).

Conclude the proof

We have shown that if \(3 | n\) then \(3 | n^{2}\), which is the contrapositive of the original statement. By showing that the contrapositive statement is true, we have proven that the original statement is true because they are logically equivalent.

Key concepts

Proof by Contraposition

Understanding proof by contraposition is like learning a secret shortcut in logic. It's a clever method to prove a statement of the form 'If P, then Q' by flipping it around and showing that 'If not Q, then not P' is true instead. It's like proving that if you don't have the effect, then you couldn't have started with the cause.

In the context of our exercise, the original conditional statement is: If \(3 mid n^2\), then \(3 mid n\). Its contrapositive swaps and negates both conditions, resulting in: If \(3 | n\), then \(3 | n^2\). Proving this alternate statement establishes the truth of the original, thanks to a principle that says a statement and its contrapositive are always both true or both false.

Why Use Contraposition?

It's all about simplicity. Sometimes, the direct approach to proving 'If P, then Q' is tangled and complex. By using contrapositive proof, you often end up with an easier path, dealing with more straightforward or more familiar principles. For students grappling with complex mathematical statements, this contrapositive 'trick' is a highly valuable tool in your proof toolkit.

Integer Divisibility

When we talk about integer divisibility, we're discussing the idea of one number being able to 'fit' into another without leaving any leftovers, just like how a neat stack of boxes fits perfectly into a storage space. For example, 6 is divisible by 3 because you can have 3 boxes, 2 times without any left outside the storage.

In our exercise, we're focused on divisibility by 3. To prove that \(3 | n^2\), you show that \(n^2\) is made up of a certain number of 3's, stacked together with none remaining. Formally, an integer \(a\) is divisible by another integer \(b\) if there exists an integer \(k\) such that \(a = b \times k\).

Applying to Our Proof

When proving the contrapositive, we state that if \(n\) is divisible by 3, i.e., \(3 | n\), it can be written as \(3k\) for some integer \(k\). When we square \(n\), the expression becomes \(9k^2\), which is also obviously divisible by 3 since it's 3 multiplied by \(3k^2\). It's like saying if a stack of boxes is grouped by threes, then a stack made of stacking those groups on top of each other will also be grouped by threes.

Mathematical Proof

A mathematical proof is a logical argument that establishes the truth of a mathematical statement beyond any doubt. Think of it as a detective presenting a case: the statement to be proven is the 'whodunit,' and the proof is the conclusive evidence that removes any reasonable doubt.

In the world of mathematics, proofs are the foundation upon which we build reliable knowledge. They can take many forms, from direct proofs to indirect methods like proof by contradiction or, as in our example, proof by contraposition, each with its own toolkit of strategies.

Structure of a Proof

A mathematical proof typically starts by stating assumptions clearly and ends by reaching a logical conclusion based on those assumptions. Between these two points lies a rigorous logical path composed of defined operations, previously established theorems, and well-known facts. This path must be clear and follow rule-bound steps, because just like a chain, the strength of a proof lies in the integrity of its links. Each step is carefully verified to ensure that the conclusion stands firm. For students, mastering the techniques of mathematical proof unlocks the ability to contribute their own proofs to the vast sea of mathematical truth.