MHB Prove that number is not a perfect square

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Square
AI Thread Summary
The discussion focuses on proving that numbers of the form 3k-1 cannot be perfect squares. Participants explore using modular arithmetic, specifically mod 3, to demonstrate that 3k-1 is congruent to 2 mod 3. They establish that perfect squares can only be congruent to 0 or 1 mod 3, leading to a contradiction. The conclusion is that showing this relationship in Z_3 suffices to prove the original statement. Overall, the use of modular arithmetic simplifies the proof process by reducing the number of cases to consider.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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?
 
Mathematics news on Phys.org
evinda said:
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...
 
I like Serena said:
Hai! :)

I would try mod 3...

I get that $(3k-1) \mod 3=-1$ or $2$..Is it right?
 
evinda said:
I get that $(3k-1) \mod 3=-1$ or $2$..Is it right?

Yes...
 
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)$?
 
I like Serena said:
Yes...

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 - - -

Deveno said:
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$
 
evinda said:
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:
 
I like Serena said:
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! :)

I like Serena said:
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?
 
evinda said:
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$.
 
  • #10
I like Serena said:
Yes. It is a complete proof, so it suffices to show it in $\mathbb{Z}_3$.

Nice..Thank you! :o
 
  • #11
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).
 
Back
Top