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

  • Thread starter number0
  • Start date
In summary: NOT WHAT THE PROBLEM ASKED FOR!!The problem did not ask for examples of x. It asked for a proof that IF x^2= 4 mod 8 THEN x= 2 mod 8. You have not given any proof at all. And, as others have said, that statement is NOT true. For example, let x= 0. Then x^2= 0 and x= 0= 2 mod 8 is certainly not true!In summary, the conversation discussed a proposed statement and its validity. The statement suggested that for all integers a, if a^2 = 4 (mod 8), then a = 2 (mod 8).
  • #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.
 
Physics news on Phys.org
  • #2


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


Hurkyl said:
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


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


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


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


Gib Z said:
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


number0 said:
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


number0 said:

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


VietDao29 said:
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


uart said:
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


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


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


Then it is correct
 
  • #15


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


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


number0 said:
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


sagardip said:
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


VietDao29 said:
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


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

1. What does the notation "a^2 = 4 (mod 8)" mean?

The notation "a^2 = 4 (mod 8)" means that the remainder when a^2 is divided by 8 is equal to 4. In other words, a^2 leaves a remainder of 4 when divided by 8.

2. How can we prove that a^2 = 4 (mod 8) implies a = 2 (mod 8)?

We can prove this by using the definition of modular arithmetic. Since a^2 = 4 (mod 8), we know that a^2 leaves a remainder of 4 when divided by 8. This means that a^2 = 8k + 4, where k is some integer. We can then substitute this into the equation a^2 = 4 (mod 8) to get (8k + 4) = 4 (mod 8). Simplifying this, we get 8k = 0 (mod 8), which means that a = 2 (mod 8) since 8k must be a multiple of 8 and a = 2 is the only integer that satisfies this condition.

3. Can you provide an example to illustrate this statement?

Sure, let's take a = 6 as an example. When we square 6, we get 36. The remainder when 36 is divided by 8 is 4, so a^2 = 4 (mod 8). Using the definition of modular arithmetic, we can see that a = 2 is the only integer that satisfies this condition, since 2^2 = 4 and 4 leaves a remainder of 4 when divided by 8.

4. Is it possible for a^2 = 4 (mod 8) and a = 2 (mod 8) to be false at the same time?

No, it is not possible for both statements to be false at the same time. If a^2 = 4 (mod 8), then by definition, a = 2 (mod 8) must be true. If a^2 does not leave a remainder of 4 when divided by 8, then a cannot be equal to 2 (mod 8).

5. How is this statement relevant in scientific research?

This statement is relevant in many areas of scientific research, particularly in fields such as cryptography, number theory, and computer science. The concept of modular arithmetic and congruence relations is important in understanding and solving complex mathematical problems. It also has practical applications in fields such as data encryption and coding theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
6
Views
981
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
988
Back
Top