# Number Theoryprove that number is not a perfect square

#### evinda

##### Well-known member
MHB Site Helper
Hey!!! Prove that no number of the form $3k-1$ is a perfect square.
Do I have to use the theorem:
"If n is a positive integer such that n mod(4) is 2 or 3, then n is not a perfect square",or is there also an other way?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey!!! Prove that no number of the form $3k-1$ is a perfect square.
Do I have to use the theorem:
"If n is a positive integer such that n mod(4) is 2 or 3, then n is not a perfect square",or is there also an other way?
Hai!! I would try mod 3...

#### evinda

##### Well-known member
MHB Site Helper
Hai!! I would try mod 3...
I get that $(3k-1) \mod 3=-1$ or $2$..Is it right?

Staff member

#### Deveno

##### Well-known member
MHB Math Scholar
What are the possible squares (mod 3)?

That is, what is:

$0^2 \text{ (mod }3)$
$1^2 \text{ (mod }3)$
$2^2 \text{ (mod }3)$?

#### evinda

##### Well-known member
MHB Site Helper
And because of the fact that $-1$ and $2$ are not perfect squares,does this mean that $3k-1$ cannot be a perfect square?Also,how can we know that,at $\mathbb{Z}_m,m\neq 3$,$3k-1 \mod m$ will not be equal to a perfect square?? - - - Updated - - -

What are the possible squares (mod 3)?

That is, what is:

$0^2 \text{ (mod }3)$
$1^2 \text{ (mod }3)$
$2^2 \text{ (mod }3)$?
$0^2 \text{ (mod }3)=0$
$1^2 \text{ (mod }3)=1$
$2^2 \text{ (mod }3)=1$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
And because of the fact that $-1$ and $2$ are not perfect squares,does this mean that $3k-1$ cannot be a perfect square?
Not in itself.
What we see is that $3k-1 \equiv 2 \pmod 3$.

Furthermore, any square must be of the form $(3r)^2, (3r + 1)^2,$ or $(3r + 2)^2$.
That means that any square is either $0$ or $1 \pmod 3$.
So we have a mismatch.
The left side always has a different remainder than the right hand side.

Also,how can we know that,at $\mathbb{Z}_m,m\neq 3$,$3k-1 \mod m$ will not be equal to a perfect square?? Is that a new question? #### evinda

##### Well-known member
MHB Site Helper
Not in itself.
What we see is that $3k-1 \equiv 2 \pmod 3$.

Furthermore, any square must be of the form $(3r)^2, (3r + 1)^2,$ or $(3r + 2)^2$.
That means that any square is either $0$ or $1 \pmod 3$.
So we have a mismatch.
The left side always has a different remainder than the right hand side.
I understand..Thanks a lot!!! Is that a new question? No,I was just wondering if it suffices,showing it in $\mathbb{Z}_3$,but I think it does,right?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
No,I was just wondering if it suffices,showing it in $\mathbb{Z}_3$,but I think it does,right?
Yes. It is a complete proof, so it suffices to show it in $\mathbb{Z}_3$.

#### evinda

##### Well-known member
MHB Site Helper
Yes. It is a complete proof, so it suffices to show it in $\mathbb{Z}_3$.
Nice..Thank you!!! #### Deveno

##### Well-known member
MHB Math Scholar
This is one of the reasons why we use "integers mod n" in number theory.

In the integers (mod n), we have "fewer cases", if we show a certain relationship is impossible in the integers (mod n), sometimes this suffices to show that same relationship is impossible in the integers.

For example, if:

$a = b^2$ in the integers, then:

$a = b^2\text{ (mod }n)$

as well, so if the second is impossible, the first is, as well.

In this example, we have $a = 3k - 1$. Now this is a lot of integers:

$a = \dots,-4,-1,2,5,8,\dots$

and the sheer number of cases to check is quite large (infinite). Going integer-by-integer to see if $a$ is a perfect square seems inefficient.

On the other hand, we have:

$a = 3k - 1 = -1 = -1 + 3 = 2\text{ (mod }3)$

which is just ONE case to check. And in that one case, we see no appropriate $b$ exists (There are only 3 possible values of $b$ mod 3 to test).