How can I check if there is a solution?

[evinda]

Hello! (Wave)

I want to check if the equation $x^2=-1$ in $\mathbb{Z}_2$ has a solution.

$$x^2 \equiv -1 \pmod 2 \Rightarrow x^2 \equiv 1 \pmod 2$$

$$\forall p>2: \left ( \frac{1}{p}\right)=1, \text{ so there is a solution.}$$

But, what happens for $p=2$? How can I check if there is a solution?

 

[Euge]

Hello! (Wave)

I want to check if the equation $x^2=-1$ in $\mathbb{Z}_2$ has a solution.

$$x^2 \equiv -1 \pmod 2 \Rightarrow x^2 \equiv 1 \pmod 2$$

$$\forall p>2: \left ( \frac{1}{p}\right)=1, \text{ so there is a solution.}$$

But, what happens for $p=2$? How can I check if there is a solution?

Hi evinda,

Since $1^2 = 1 = -1$ in $\Bbb Z_2$, the equation $x^2 = -1$ has a solution in $\Bbb Z_2$. The Legendre symbol calculation you've made does not relate to the existence of solutions to $x^2 = -1$ over $\Bbb Z_2$.

 

[evinda]

Hi evinda,

Since $1^2 = 1 = -1$ in $\Bbb Z_2$, the equation $x^2 = -1$ has a solution in $\Bbb Z_2$. The Legendre symbol calculation you've made does not relate to the existence of solutions to $x^2 = -1$ over $\Bbb Z_2$.

A ok.. We see that a solution is $x=1$, but how can we prove it? (Thinking)

 

[Euge]

It's already done; the equations $1^2 = 1 = -1$ show directly that $x^2 = -1$ has a solution at $x = 1$.

 

[mathbalarka]

What you have to understand is that there is essentially no class called "-1 modulo 2". Under modulo 2 identifications, it's already identified with the set 1 modulo 2 of $\Bbb N$.

So your equation is essentially $x^2 = 1$ modulo 2, which clearly has solutions ($x = 1$) and the whole solution set itself is 1 modulo 2 as you can see.

 

[mathbalarka]

Goodness. By $\Bbb Z_2$ you don't mean 2-adic integers, do you?

 

[evinda]

Goodness. By $\Bbb Z_2$ you don't mean 2-adic integers, do you?

If so, what is the difference? (Worried)

 

[mathbalarka]

Surely 2-adic integers are not isomorphic to cyclic group of order 2! Please clarify what you mean, $\Bbb Z_2$ or $\mathbf{Z}_2$.

 

[evinda]

Surely 2-adic integers are not isomorphic to cyclic group of order 2! Please clarify what you mean, $\Bbb Z_2$ or $\mathbf{Z}_2$.

Now I saw that the equation is also written like that: $x^2 \equiv -1 \pmod 2$..

So, $\mathbb{Z}_2$ is meant, right?

Can I justify that $1$ is the only solution like that?

The only number that satisfies $(a,2)=1$ in $\mathbb{Z}_2$ is the number $1$.
This number satisfies also the equation $x^2 \equiv 1 \pmod 2$, therefore it is the only solution.

(Thinking)

 

[Siron]

Can I justify that $1$ is the only solution like that?

I'm not an algebraist but in my opinion the point is that $\mathbb{Z}_2$ is a finite set hence to show that the equation $x^2=-1$ has a solution in $\mathbb{Z}_2$ you just can plug in the elements of $\mathbb{Z}_2$ successively and check if they satisfy the equation which is only true for $x=1$. Therefore $x=1$ is the only solution in $\mathbb{Z}_2$.

 

[evinda]

I'm not an algebraist but in my opinion the point is that $\mathbb{Z}_2$ is a finite set hence to show that the equation $x^2=-1$ has a solution in $\mathbb{Z}_2$ you just can plug in the elements of $\mathbb{Z}_2$ successively and check if they satisfy the equation which is only true for $x=1$. Therefore $x=1$ is the only solution in $\mathbb{Z}_2$.

So, can I justify it like that?

$$x^2 \equiv -1 \pmod 2 \Rightarrow x^2 \equiv 1 \pmod 2$$

$$\mathbb{Z}_2=\{0,1 \}$$

For $x=0: x^2 \equiv 1 \pmod 2 \Rightarrow 0 \equiv 1 \pmod 2$, that does not stand.

For $x=1: x^2 \equiv 1 \pmod 2 \Rightarrow 1 \equiv 1 \pmod 2$, that is true.

Therefore, the only solution of the equation is $x=2$.

 

[mathbalarka]

Yes, that's it. You can verify like that if $x = 0 \pmod 2$ then $x^2 \not = 1 \pmod 2$ and if $x = 1 \pmod 2$ then $x^2 = 1 \pmod 2$. Thus $x = 1 \pmod 2$ is the only solution to $x^2 = -1 = 1 \pmod 2$

 

[evinda]

Yes, that's it. You can verify like that if $x = 0 \pmod 2$ then $x^2 \not = 1 \pmod 2$ and if $x = 1 \pmod 2$ then $x^2 = 1 \pmod 2$. Thus $x = 1 \pmod 2$ is the only solution to $x^2 = -1 = 1 \pmod 2$

Nice, thank you very much! (Smile)

The exercise asks to find the first three positions of the solution, that means that we are looking for a solution $\pmod 2$, one solution $\pmod{2^2}$ and one $\pmod {2^3}$.

That's what I have tried:

$$x_0=1$$

We are looking for a $x_1 \in \mathbb{Z}$ such that:$$x_1^2 \equiv -1 \pmod {2^2} \text{ such that } x_1 \equiv 1 \pmod 2$$

$$x_1 \equiv 1 \pmod 2 \Rightarrow 2 \mid x_1-1 \Rightarrow \exists a_1 \in \mathbb{Z} \text{ such that } x_1=1+2a_1$$

$$x_1^2+1=(1+2a_1)^2+1 \equiv 2 \pmod {2^2}$$

So: $x_1^2+1 \equiv 0 \pmod{2^2} \Leftrightarrow 2 \equiv 0 \pmod {2^2}$, that is a contradiction.Is it right or have I done something wrong? (Thinking)

 

[mathbalarka]

$-1 = 3$ is not a quadratic residue modulo $2^2 = 4$. There is no solution to $x^2 = -1 \pmod {2^2}$.

 

[evinda]

$-1 = 3$ is not a quadratic residue modulo $2^2 = 4$. There is no solution to $x^2 = -1 \pmod {2^2}$.

So, can we not apply the Hensel Lifting Lemma in this case? (Thinking)

 

[mathbalarka]

Derivative of $x^2 + 1$ vanishes modulo $2$. It's not possible to apply Hensel's lemma in this case, yes.

 

[evinda]

Derivative of $x^2 + 1$ vanishes modulo $2$. It's not possible to apply Hensel's lemma in this case, yes.

You mean at the first position of the solution? (Thinking)

 

[mathbalarka]

Not sure what you mean by that. How would you state Hensel's lemma? If I haven't forgotten all the elementary number theory I did, I trust nonvanishing of $f'(x)$ modulo $p$ is an essential condition.

 

[evinda]

Not sure what you mean by that. How would you state Hensel's lemma? If I haven't forgotten all the elementary number theory I did, I trust nonvanishing of $f'(x)$ modulo $p$ is an essential condition.

We haven't done the theory in class, the prof explained it to us, using an example.. So, in this case, there is just the first postion of the solution?

 

[evinda]

If so, how can it be justified? (Worried)

 

[evinda]

Is my justification of the post #13, where I found a contradiction, right? (Thinking)

 

[mathbalarka]

I don't know what you're trying to justify, but you have just shown that Hensel's lemma cannot be applied to $x^2 + 1$ modulo $2$. Is that what you wanted to show?

 

[evinda]

I don't know what you're trying to justify, but you have just shown that Hensel's lemma cannot be applied to $x^2 + 1$ modulo $2$. Is that what you wanted to show?

I wanted to find a solution $\pmod 2$, a solution $\pmod {2^2}$ and a solution $\pmod {2^3}$.

But, since we get to a contradiction, when we want to apply Hensel's lemma, in order to find a solution $\pmod {2^2}$, that means that the equation $x^2=-1$ has not solutions $\pmod {2^n},n>1$, right? (Thinking)

 

[mathbalarka]

Yes, that is correct, $x^2 + 1$ has no solution modulo $2^2$. Hensel's lemma fails in this case (the derivative evaluates to 0 modulo $2^2$)

 

[evinda]

Yes, that is correct, $x^2 + 1$ has no solution modulo $2^2$. Hensel's lemma fails in this case (the derivative evaluates to 0 modulo $2^2$)

And from this, we also know that it has no solution $\pmod {2^3}$, right? (Thinking)

 

[mathbalarka]

Yes, as having a solution modulo 8 automatically implies existence of a solution modulo 4.

 

[evinda]

Yes, as having a solution modulo 8 automatically implies existence of a solution modulo 4.

I understand.. thanks a lot! (Smile)