To prove by contradiction that if $n^2$ is divisible by 3, then $n$ is divisible by 3, we proceed as follows:

Step 1: Assume the opposite (Contradiction Hypothesis)

We assume the opposite of the statement we want to prove. Specifically, assume:

• $n^2$ is divisible by 3.
• $n$ is not divisible by 3.

Step 2: Analyze the assumption that $n$ is not divisible by 3

If $n$ is not divisible by 3, then $n$ must be congruent to either 1 or 2 modulo 3. In other words, we have two cases to consider:

• $n \equiv 1 \pmod{3}$
• $n \equiv 2 \pmod{3}$

Step 3: Consider the possible values of $n^2$ modulo 3

• Case 1: $n \equiv 1 \pmod{3}$

  • If $n \equiv 1 \pmod{3}$, then $n^2 \equiv 1^2 = 1 \pmod{3}$.
  • This means $n^2$ is not divisible by 3.

• Case 2: $n \equiv 2 \pmod{3}$

  • If $n \equiv 2 \pmod{3}$, then $n^2 \equiv 2^2 = 4 \equiv 1 \pmod{3}$.
  • Again, $n^2$ is not divisible by 3.

Step 4: Reach a contradiction

We assumed that $n^2$ is divisible by 3, but in both cases above, we see that if $n$ is not divisible by 3, then $n^2$ is not divisible by 3 either. This contradicts the assumption that $n^2$ is divisible by 3.

Step 5: Conclusion

Since assuming that $n$ is not divisible by 3 leads to a contradiction, we must conclude that $n$ must be divisible by 3 if $n^2$ is divisible by 3.

Thus, the statement is proven by contradiction: If $n^2$ is divisible by 3, then $n$ is divisible by 3.

---

Would you like any further details or clarifications? Here are some related questions:

1. What does it mean for a number to be divisible by 3?
2. How does the principle of proof by contradiction work in general?
3. What other number properties can we prove using similar logic (e.g., divisibility by other primes)?
4. Can you prove that if $n^2$ is divisible by any prime $p$, then $n$ must also be divisible by $p$?
5. How would this proof change if we were working with other primes, such as 5?

Tip: Proof by contradiction is often useful in number theory, especially when trying to prove divisibility or properties of numbers based on assumptions.