Skip to main content
add the symmetry argument to the answer; feel free to improve
Source Link
Ilmari Karonen
  • 46.5k
  • 5
  • 111
  • 187

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

By simple arithmetic, one can see that $r < n/2 \iff n-r > n/2$. Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

By simple arithmetic, one can see that $r < n/2 \iff n-r > n/2$. Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.

deleted 3 characters in body
Source Link
Thomas
  • 7.5k
  • 1
  • 31
  • 44

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

SinceIf there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

Since there are exactly four roots (each prime factor brings in two roots, well, one root and its conjugate) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

Source Link
Thomas
  • 7.5k
  • 1
  • 31
  • 44

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

Since there are exactly four roots (each prime factor brings in two roots, well, one root and its conjugate) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.