# Homework Help: Modular Arithmetic

1. May 12, 2012

### mike1

1. The problem statement, all variables and given/known data

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

2. Relevant equations

3. 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?

2. May 12, 2012

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

3. May 12, 2012

### I like Serena

Welcome to PF, mike!

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

4. May 12, 2012

### mike1

Sorry, still confused :(

5. May 12, 2012

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

6. May 12, 2012

### mike1

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

7. May 12, 2012

### I like Serena

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

8. May 12, 2012

### mike1

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

9. May 12, 2012

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

10. May 12, 2012

### mike1

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

11. May 12, 2012

### I like Serena

Yep. :)

12. May 12, 2012

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

13. May 12, 2012

### I like Serena

What are the possible remainders of m^2?

14. May 12, 2012

### mike1

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

15. May 12, 2012

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

16. May 12, 2012

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

Last edited: May 12, 2012
17. May 12, 2012

### I like Serena

Perhaps compare it to that?

18. May 13, 2012

### 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)?...

19. May 13, 2012

### Office_Shredder

Staff Emeritus
If we had 3m2=n2+1, then we know that 3m2=n2+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?

20. May 13, 2012

### mike1

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

Last edited: May 13, 2012
21. May 14, 2012

### mike1

Ignore...

Last edited: May 14, 2012
22. May 14, 2012

### I like Serena

Almost.
You should have different numbers...

23. May 14, 2012

### mike1

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

24. May 14, 2012

Good!