Proof of if $a^2$ is divisible by 4, then a is not. 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.
 A: 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$.
