Vrftsjtryk

Hint: $p|ab implies p|a$ or $p|b$ if $p$ is a prime

if $nequiv 0,1,2 mod 3$ then $n^2equiv 0,1 mod 3$ therefore $n^2equiv 0mod 3$ then $n equiv 0 mod 3$

For every $ninmathbb Z$ you have three possible cases. Either $n=3k$ or $n=3k+1$ or $n=3k+2$ (for some $kinmathbb Z$).

Let us consider each of these cases separately:

• If $n=3k$, then $n^2=(3k)^2=3(3k^2)$, which means $3mid n^2$.


• If $n=3k+1$, then $n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1$. This implies $3nmid n^2$.


• If $n=3k+2$, then $n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$. So we have again $3nmid n^2$.

So we see that if $3nmid n$ (i.e., in the last two cases), then $3nmid n^2$. This is the same as saying that $3mid n^2$ implies $3mid n$.

Notice that we have in fact proved also that if $3nmid n$, then the remainder of $n^2$ modulo $3$ is $1$.

Once you learn a bit about congruences, you will be able to write down arguments like this in more elegant and more economical way.
This is the way it was done in this answer.

Maybe it is also worth to mention that instead of $n=3k+2$ we can use $n=3k-1$. This can sometimes simplify the calculations slightly. (In this case we get $n^2=(3k-1)^2=9k^2-6k+1=3(3k^2-2k)+1$.)

Proof by contrapositive:
("If $3 not mid n$, then $ 3 not mid n^2 $" is logically equivalent to "If $3mid n^2$, then $ 3mid n $")

Since we have $3 not mid n$, then there are remainders $r=1,2$ So, we have that $n=3k_1+1$ or $n=3k_2+2$ for some $k_1,k_2 in mathbb{N}$.

Then, if $n=3k_1+1$ we have that $n^2=9k_1^2+6k_1+1$. Note $n^2=3(3k_1^2+2k_1)+1$, where $3k_1^2+2k_1 in mathbb{N}$, since $mathbb{N}$ closed under multiplication and addition. So, since we have remainder $r=1$ we see that $3 notmid n^2$.

Then, if $n=3k_2+2$ we have that $n^2=9k_2^2+12k_2+4$. Note $n^2=3(3k_2^2+4k_2+1)+1$, where $3k_2^2+4k_2+1in mathbb{N}$ since $mathbb{N}$ closed under multiplication and addition. So, since we have remainder $r=1$ we see that $3 notmid n^2$

Thus, we have that $3 notmid n^2$, which shows the contrapositive to be true.

Q.E.D.

$n$ is an integer, so by Euclid's algorithm, $n=3a+b$ where $a$ is an integer, and $b$ is either 0,1 or 2, then $n^2=9a^2+6ab+b^2$, and therefore $3|n^2Rightarrow 3|b^2$. And now we got Dr. Sonhard Graubner proof as $3|b^2Rightarrow b^2neq 1,4Rightarrow bneq 1,2 Rightarrow b=0Rightarrow n=3aRightarrow 3|n$

As fan wrote, if $p$ is prime and divides $ab$ then $p$ divides either $a$ or $b$ (or both). Here is a proof of that theorem.

Since the only divisors of a prime number are $1$ and itself, either $GCD(p,a)=1$ or $GCD(p,a)=p$. (GCD means Greatest Common Divisor.) The second means that $p$ divides $a$ and we're done.

If $GCD(p,a)=1$ then by Bezout's theorem we can find integers $x$ and $y$ such that
$$px+ay=1$$
Multiply this by $b$ and we get
$$pbx+(ab)y=b$$

$p$ obviously divides the first term and by hypothesis it divides the second, so $p$ must also divide the third term, $b$, and we are done again.

Everything comes from Bézout's lemma. Suppose that $3$ does not divide $n$, then $GCD(3, n) = 1$ and there are integers $a$ and $b$ such that $3a + nb = 1$. Now if you multiply both sides by n you get $3an + n^2b = n$. $3$ divides the left hand side, so it divides $n$ too, which gives the desired contradiction.

nnn + 2*n = n*(nn+2) = n{(n*n -1) + 3} = n*3 + {n*(n-1)*(n+1)} ==> P + Q

Here
P = n*3 ==> divisible by 3
Q = (n-1)n(n+1) ==> this is multiplication of three consecutive number and hence it is divisible by 3
==> P + Q is divisible by 3