Prove if a^2 = 4 (mod 8) then a = 2 (mod 8)

[number0]

Prove "if a^2 = 4 (mod 8) then a = 2 (mod 8)"

Homework Statement

For all integers a, if a² = 4 (mod 8), then a = 2 (mod 8).

Homework Equations

a = b (mod n) means a = b + nk

where a, b, and k are integers and n is a natural number.

The Attempt at a Solution

Since a^2 = 4 (mod 8), I wrote a^2 = 8n + 4. Then a^2 = 4(2n + 1).

This is where I got stuck... The only non-efficient method I can think of is to substitute n for some really long polynomial integer to make the square root of the equation equal 2 (mod 8). However, I believe that there should be a much more simpler and efficient approach to it. Does anyone have any tips? Thanks.

 

[Hurkyl]

Honestly, I would just try all 8 values of a and be done with it.

 

[number0]

Honestly, I would just try all 8 values of a and be done with it.

What do you mean by it? Exhaust the list of possible a values?

 

[Mark44]

Yes. All integers fall into one of eight equivalence classes. Check each of the eight classes and you're done.

 

[number0]

Okay, as it turns out, I am new at proving. And I have no idea what the eight equivalence classes are. I googled what it is, and I am very certain that I am not suppose to apply the eight equivalence classes onto this proof (although it can be).

 

[Gib Z]

Basically, there are only 8 types of integers in mod 8. They are 0,1,2,3,4,5,6,7 mod 8. In other words, numbers of the form 8k, 8k+1, 8k+2 ... 8k+7. Test each one.

Example: Numbers of the form 8k+5. Square it: 64k^2 + 80k+ 25 = 8(8k^2+10k+3) + 1 , so its square is 1 mod 8. Thus, numbers of those form don't even satisfy the premise "if a^2 = 4 (mod 8) ..." , so that doesn't work. Try the other cases, see if they work.

 

[number0]

Basically, there are only 8 types of integers in mod 8. They are 0,1,2,3,4,5,6,7 mod 8. In other words, numbers of the form 8k, 8k+1, 8k+2 ... 8k+7. Test each one.

Example: Numbers of the form 8k+5. Square it: 64k^2 + 80k+ 25 = 8(8k^2+10k+3) + 1 , so its square is 1 mod 8. Thus, numbers of those form don't even satisfy the premise "if a^2 = 4 (mod 8) ..." , so that doesn't work. Try the other cases, see if they work.

I see... is there any other way than exhausting the list?

 

[uart]

I see... is there any other way than exhausting the list?

Well try the "exhaustive" method first and you'll quickly see that the conjecture is false, so no it cannot be proven.

 

[VietDao29]

Homework Statement

For all integers a, if a² = 4 (mod 8), then a = 2 (mod 8).

Homework Equations

a = b (mod n) means a = b + nk

where a, b, and k are integers and n is a natural number.

The Attempt at a Solution

Since a^2 = 4 (mod 8), I wrote a^2 = 8n + 4. Then a^2 = 4(2n + 1).

This is where I got stuck... The only non-efficient method I can think of is to substitute n for some really long polynomial integer to make the square root of the equation equal 2 (mod 8). However, I believe that there should be a much more simpler and efficient approach to it. Does anyone have any tips? Thanks.

I'm not sure if you copied the problem down correctly, but it doesn't look quite right to me.

We have:
6 ^ 2 = 36 \equiv 4 \mbox{ mod } 8
but
6 \not{\equiv} 2 \mbox{ mod } 8.

 

[uart]

I'm not sure if you copied the problem down correctly ...

I beat you by one minute. :)

But I was hoping to leave it to the OP to find case that demonstrated the conjecture false. After all, this is a homework section.

 

[number0]

I beat you by one minute. :)

But I was hoping to leave it to the OP to find case that demonstrated the conjecture false. After all, this is a homework section.

I am sure that I copied the homework question correctly... Not only that, but there was a theorem later in the book that proves that the proposition is correct. The only thing that is different is that the equal signs for both a² = 4 (mod 8) and a = 2 (mod 8) is supposed to be a triple equal sign (signifying congruence).

 

[sagardip]

the given conjecture is wrong as for any positive integer a we have
a=0,1,2,3,4,-3,-2,-1(mod8) now squaring both sides we get
a^2=0,1,4(mod8) . See there is no remainder 2

 

[sagardip]

sorry i am wrong. If a^2=4(mod8) then obviously a=2,-2(mod8). so in your question -2 should be mentioned

 

[sagardip]

Then it is correct

 

[sagardip]

the theorem must be
if a=b(mod n) then a^2=b^2(mod n)

 

[sagardip]

To all those who said that the proposition is wrong here is an example
10^2=100=4(mod8) and 10=2(mod8)

 

[VietDao29]

I am sure that I copied the homework question correctly... Not only that, but there was a theorem later in the book that proves that the proposition is correct. The only thing that is different is that the equal signs for both a² = 4 (mod 8) and a = 2 (mod 8) is supposed to be a triple equal sign (signifying congruence).

If you are sure that there's no -2 in your problem. Then I think the problem should read:
a ^ 2 \equiv 4 \mbox{ mod } 8 \Rightarrow a \equiv 2 \mbox{ mod } 4.
It should be 4 instead of 8. :)

Which means that you only needs to consider 4 cases: a \equiv 0; 1; 2; 3 \mbox{ mod } 4.

You should ask your professor to check that problem. I strongly believe that the statement in the problem is incorrect!

 

[HallsofIvy]

To all those who said that the proposition is wrong here is an example
10^2=100=4(mod8) and 10=2(mod8)

What that proves is that you haven't understood the problem and you haven't understood what people here are saying.

Your examples show that there exist x such that x^2= 4 and that x= 2 mod 8. Yes, that is true but it is NOT the problem you stated. The problem you stated is that for all x, "if x^2= 4 mod 8, then x= 2 mod 8" and, as people have been telling you, that is NOT true. What is true is that "if x^2= 4 mod 8, then x= 2 OR x= -2 mod 8". And -2= 8- 2= 6 mod 8.

 

[number0]

If you are sure that there's no -2 in your problem. Then I think the problem should read:
a ^ 2 \equiv 4 \mbox{ mod } 8 \Rightarrow a \equiv 2 \mbox{ mod } 4.
It should be 4 instead of 8. :)

Which means that you only needs to consider 4 cases: a \equiv 0; 1; 2; 3 \mbox{ mod } 4.

You should ask your professor to check that problem. I strongly believe that the statement in the problem is incorrect!

Okay, I just looked at the problem again, and I am 100% sure that I stated the problem as it is written inside the book. I am going to ask my professor tomorrow and see what he says.

 

[Mark44]

Often, problems like this are prefaced with the request to either prove the statement or find a counterexample. Are there instructions like this for your problem?

A counterexample here is x = -2.

(-2)² = 4 \equiv 4 (mod 8), but x \equiv 6 (mod 8).