1

The exercise verbatim:

Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and $p$, find one possible value of $x$. (Hint: Write $p$ as $p = 4k +3$ and use Euler's Criterion. You might have to multiply two sides of an equation by $n$ at one point.)

Euler's Criterion says that if $a \equiv x^2 \pmod p$ then $a^{\frac {p-1}2} \equiv 1\pmod p$, so we know $n^{\frac {p-1}2} \equiv 1\pmod p$.

The way I understand, one is supposed to isolate $x$ against known things. I could not do it, neither could find how to make use of $p = 4k +3$ or where to multiply the two sides of an equation by $n$ in a way that helps.

How can we find $x$?

aristotle85
  • 115

2 Answers2

2

As you said, $n^{\frac{p-1}{2}}\equiv 1\pmod{\! p}$. Then $p=4k+3$ implies $n^{2k+1}\equiv 1\pmod{\! p}$. Multiply both sides by $n$, get $n\equiv (n^{k+1})^2\pmod{\! p}$.

user26486
  • 11,331
  • By multiplying $n^{2k+1}\equiv 1\pmod{! p}$ by I thought one gets $n^{2k+2}\equiv n \pmod p$. Is inverting the sides ok? – aristotle85 Jun 04 '15 at 21:44
  • @aristotle85 Yes, $a\equiv b\pmod{! n},\Leftrightarrow, b\equiv a\pmod{! n}$, because $n\mid a-b,\Leftrightarrow, n\mid b-a=-(a-b)$. Modular congruence is an equivalence relation, so it is symmetric. – user26486 Jun 04 '15 at 21:49
  • @aristotle85 $a\equiv b\pmod{! n}$ tells you $a,b$ leave the same remainders when divided by $n$, which makes it obvious $a\equiv b\pmod{! n},\Leftrightarrow, b\equiv a \pmod{! n}$. It says $a,b$ belong to the same congruence class. The fact modular congruence is an equivalence relation tells you the integers can be precisely divided into classes, and two elements being in the same congruence class is denoted by $\equiv$. – user26486 Jun 04 '15 at 22:16
  • It cause me some confusion since, for example, $15\equiv 1 \pmod 2$ is so because $(15-1)=7$ with remainder zero, so I assumed, incorrectly as it seems, that the number on the left side of the congruence must be the bigger number. – aristotle85 Jun 04 '15 at 22:52
  • @aristotle85 You mean $(15-1)=7\cdot 2$. Also, $(1-15)=(-7)\cdot 2$. It only matters $-7$ is an integer. $1\equiv 15\pmod{! 2},\Leftrightarrow, 2\mid 1-15$, which is true by the exact definition of divisibility: $1-15=2(-7)$. Definition: $n\mid a,\Leftrightarrow, n=ak$ for some $k\in\Bbb Z$. – user26486 Jun 04 '15 at 23:02
1

Try $x=n^{\frac{p+1}{4}}$, and use Euler's Criterion. The shape $4k+3$ part is to make $\frac{p+1}{4}$ an integer.

André Nicolas
  • 507,029
  • Using $x=n^{\frac{p+1}{4}}$ one gets the value since n and p are given. But I could not find how to get $x=n^{ \frac {p+1}{4} }$ – aristotle85 Jun 04 '15 at 21:41
  • I think it is fairly natural, $n^{(p-1)/2}$ is congruent to $1$, so $n^{p+1)/2}$ is congruent to $n$, but $(p+1)/2$ is even. There is a similar but substantially more complicated trick for $p$ of the form $8k+5$. However, there is no nice trick for $p$ of the form $8k+1$. – André Nicolas Jun 04 '15 at 21:50
  • It seems that $x=n^{\frac {p+1}{4}}$ comes somehow form the fact that $\sqrt {n^{\frac {p+1}{2}}}$ is equal to $n^{\frac {p+1}{4}}$. But I can't make the jump from $n\equiv x^2$ to $x=\sqrt n$. – aristotle85 Jun 04 '15 at 22:46
  • The jump can't quite be made, since in general there are two square roots. The negative of the answer I wrote would also work. Apart from that, if you put $x^2$ in for $n$, the jump comes naturally. However, in the proof I did not make that jump. One verifies by a direct computation that $n^{(p+1)/4}$ works. This is kind of like verifying that $4$ is a square root of $16$ by calculating $4\times 4$. – André Nicolas Jun 04 '15 at 22:53