Welcome to our community

Be a part of something great, join today!

Number Theory prove that number is not a perfect square

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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
Mar 5, 2012
8,780
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
Apr 13, 2013
3,720

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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
Apr 13, 2013
3,720
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?? (Thinking)

- - - 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
Mar 5, 2012
8,780
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?? (Thinking)
Is that a new question? :confused:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :confused:
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
Mar 5, 2012
8,780
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
Apr 13, 2013
3,720

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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).