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

  • Thread starter number0
  • Start date
  • #1
number0
104
0
Prove "if a^2 = 4 (mod 8) then a = 2 (mod 8)"

Homework Statement



For all integers a, if a2 = 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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19


Honestly, I would just try all 8 values of a and be done with it.
 
  • #3
number0
104
0


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?
 
  • #4
36,216
8,199


Yes. All integers fall into one of eight equivalence classes. Check each of the eight classes and you're done.
 
  • #5
number0
104
0


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).
 
  • #6
Gib Z
Homework Helper
3,346
6


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.
 
  • #7
number0
104
0


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???
 
  • #8
uart
Science Advisor
2,797
21


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.
 
  • #9
VietDao29
Homework Helper
1,424
3


Homework Statement



For all integers a, if a2 = 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:
[tex]6 ^ 2 = 36 \equiv 4 \mbox{ mod } 8[/tex]
but
[tex]6 \not{\equiv} 2 \mbox{ mod } 8[/tex].
 
  • #10
uart
Science Advisor
2,797
21


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.
 
  • #11
number0
104
0


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 a2 = 4 (mod 8) and a = 2 (mod 8) is supposed to be a triple equal sign (signifying congruence).
 
  • #12
sagardip
38
0


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
 
  • #13
sagardip
38
0


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


Then it is correct
 
  • #15
sagardip
38
0


the theorem must be
if a=b(mod n) then a^2=b^2(mod n)
 
  • #16
sagardip
38
0


To all those who said that the proposition is wrong here is an example
10^2=100=4(mod8) and 10=2(mod8)
 
  • #17
VietDao29
Homework Helper
1,424
3


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 a2 = 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:
[tex]a ^ 2 \equiv 4 \mbox{ mod } 8 \Rightarrow a \equiv 2 \mbox{ mod } 4[/tex].
It should be 4 instead of 8. :)

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

You should ask your professor to check that problem. I strongly believe that the statement in the problem is incorrect!!!
 
Last edited:
  • #18
HallsofIvy
Science Advisor
Homework Helper
43,010
969


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 [itex]x^2= 4[/itex] 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 [itex]x^2= 4[/itex] mod 8, then x= 2 mod 8" and, as people have been telling you, that is NOT true. What is true is that "if [itex]x^2= 4[/itex] mod 8, then x= 2 OR x= -2 mod 8". And -2= 8- 2= 6 mod 8.
 
  • #19
number0
104
0


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

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

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.
 
  • #20
36,216
8,199


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)2 = 4 [itex]\equiv[/itex] 4 (mod 8), but x [itex]\equiv[/itex] 6 (mod 8).
 

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

  • Last Post
Replies
1
Views
1K
Replies
13
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
11
Views
4K
Top