Proof of if $a^2$ is divisible by 4, then a is not.

Question

Hello I am new to proofs.

I was wondering about how one can create a false prove regarding the irrationality of $\sqrt4$ using the contradiction method.I wrote the fake proof and was analysing where I have made a mistake.

I found this as one of the answers.

Just because $a^2$ is divisible by 4, that doesn't mean $a$ is.

I was trying to prove why this is true, without giving examples (eg. $4|6^2$ but not $4|6$).

Okay, so Euclid's theorem states that:

If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

So the main question is what if $p$ is a non-prime or composite number? Is there a mathematical explanation on why it fails?

I sincerely appreciate your contributions.

Answer 1

You want to prove this statement:

Just because $a^2$ is divisible by $4$, that doesn't mean $a$ is.

A way to say this which is a little easier to reason about logically is

It is not true that for every integer $a,$ if $4 \vert a^2$ then $4 \vert a.$

In logical notation,

$$ \lnot \forall a \in \mathbb Z .((4 \vert a^2) \implies (4 \vert a)).$$

This is equivalent to

$$ \exists a \in \mathbb Z . \lnot((4 \vert a^2) \implies (4 \vert a)) $$

which in turn is equivalent to

$$ \exists a \in \mathbb Z . ((4 \vert a^2) \land \lnot (4 \vert a)). $$

A perfectly legitimate way to prove an "exists" statement is by showing a witness of the statement, in this case an example of an integer $a$ for which the inner statement $(4 \vert a^2) \land \lnot (4 \vert a)$ is true. The integer $a = 6$ is such a witness. An even simpler witness is $a = 2.$

The witness or example of the "exists" statement is a counterexample of the original (not negative) "for all" statement.

In other words, a counterexample of the statement

If $a^2$ is divisible by $4$ then $a$ is

is a mathematical explanation of why the statement fails. It is also a mathematical explanation of why the statement

If $p\vert ab$, then $p\vert a$ or $p\vert b$

fails when we do not require $p$ to be a prime number.

---

If you want to dig a little deeper into this, however, you might want to determine precisely what is the set $S$ of integers $n$ such that if $n\vert ab$, then $n\vert a$ or $n\vert b$.

Obviously $S$ contains all the primes, but are any other numbers in $S$?

Let $n$ be an integer and consider the prime factorization of $n$:

$$ n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} $$

where $p_1, p_2, \ldots, p_m$ are $m$ distinct primes and $k_1, k_2, \ldots, k_m$ are positive integers.

If $n$ is a prime then $m = 1$ and $k_1 = 1$, and it is true that for all integers $a$ and $b,$ if $n\vert ab$, then $n\vert a$ or $n\vert b$.

You initially were looking at divisibility by $n = 4.$ In that case $m = 1$ but $k_1 = 2,$ because the prime factorization of $n = 4$ is $n = 2^2.$

You could try generalizing your counterexample for $4$ to a counterexample for any prime. What you need to prove then is that for every number $n$ of the form $n = p^2$ where $p$ is prime, there exists an integer $a$ such that $n\vert a^2$ is true but $n \vert a$ is false.

In fewer words, for every prime $p,$ there exists an integer $a$ such that $p^2\vert a^2$ is true but $p^2 \vert a$ is false.

What about higher powers of $p$?

What about the product of two distinct primes, $n = p_1 p_2$?

Eventually you might be able to come up with a simple test that can be applied to any integer $n$ and that will tell you in a finite number of steps (without needing to actually try every pair of integers $a$ and $b$) whether it is true for every pair of integers $a$ and $b$ that if $n\vert ab$, then $n\vert a$ or $n\vert b$.