Proving Impossibility of Integer n in Modular Arithmetic

[mike1]

Homework Statement

Prove that it is impossible to find an integer n, such that

n^2 = 2 mod(4) or n^2 = 3 mod(4)

Hence or otherwise, prove that there do not exist integers m and n such that

3m^2 - 1 = n^2

Homework Equations

The Attempt at a Solution

Since n must be congruent to each of 0,1,2,3, n^2 must be congruent to 0,1,4,9 but what do I do next to prove this?

 

[Karamata]

Well, if (for example) n^2 \equiv 9\pmod 4, and you know that 9 \equiv 1\pmod 4,then you can tell that n^2 \equiv ??\pmod 4

 

[I like Serena]

Homework Statement

Prove that it is impossible to find an integer n, such that

n^2 = 2 mod(4) or n^2 = 3 mod(4)

Hence or otherwise, prove that there do not exist integers m and n such that

3m^2 - 1 = n^2

Homework Equations

The Attempt at a Solution

Since n must be congruent to each of 0,1,2,3, n^2 must be congruent to 0,1,4,9 but what do I do next to prove this?

Welcome to PF, mike!

Can you simplify 0,1,4,9 mod 4?
Is any of those congruent to 2 or to 3?

 

[mike1]

Sorry, still confused :(

 

[I like Serena]

As you say, n^2 must be congruent to one of 0,1,4,9.

Writing something "mod 4", means you are only interested in the remainder after division by 4.
What is the remainder if you divide for instance 9 by 4?

 

[mike1]

So: 9 = 1 mod(4), since 9-1 = 8/4=2

 

[I like Serena]

Yep.
So what are the remainders of 0,1,4,9?

 

[mike1]

0= mod(4)
1= mod(4)
4= 0 mod(4)
9= 1 mod(4)

 

[I like Serena]

If you divide 1 by 4, it cannot be divided and the remainder is just 1.
The same for zero.

So your remainders for n^2 are 0,1,0,1.
Is any of those congruent to 2 or to 3?

 

[mike1]

No, because 0/4 or 1/4 is not 2 or 3? & hence it's impossible to find an integer to satisfy it?

 

[I like Serena]

Yep. :)

 

[mike1]

Thanks :)

For part b) Since n^2 is congruent to 0 or 1 mod(4), after re-arranging we see that
3m^2 = n^1+1, so then n^2 + 1 is congruent to 1 or 2 mod(4). What should be done about the 3m^2?

 

[I like Serena]

What are the possible remainders of m^2?

 

[mike1]

Is it 0,1,4,9 but then times by 3 so 0,3,12,27? Or is that completely wrong..

 

[I like Serena]

Oh that is correct.
But didn't we conclude that 0,1,4,9 were congruent to 0,1,0,1?

Multiply that with 3!

 

[mike1]

Oh! So the remainders of 3m^2 are 0,3,0,3. So 3m^2 is congruent to 0 or 3 mod(4), but how we combine both of expressions?

 

[I like Serena]

Well, you already had:

n^2 + 1 is congruent to 1 or 2 mod(4).

Perhaps compare it to that?

 

[mike1]

How do I compare it to that?
Can I say since 3m^2=n^2+1, then 3m^2 is congruent to 0,1,2,3 mod(4)?...

 

[Office_Shredder]

If we had 3m²=n²+1, then we know that 3m²=n²+1 (mod 4). What are the possible values of the left hand side? What are the possible values of the right hand side? (these were calculated earlier in the thread) Is it possible for the left hand and right hand side to be equal?

 

[mike1]

If we had 3m²=n²+1, then we know that 3m²=n²+1 (mod 4). What are the possible values of the left hand side? What are the possible values of the right hand side? (these were calculated earlier in the thread) Is it possible for the left hand and right hand side to be equal?

Do you mean 0,3,0,3 and 0,1,0,1?

 

[mike1]

Ignore...

 

[I like Serena]

Do you mean 0,3,0,3 and 0,1,0,1?

Almost.
You should have different numbers...
(Look back in the thread.)

 

[mike1]

Almost.
You should have different numbers...
(Look back in the thread.)

yeah, I've got it now..thanks :)

 

[I like Serena]

Good!