Created by potrace 1.14, written by Peter Selinger 2001-2017 Eύρηκω

Home

Primitive root existence

Let n be a positive integer. There exists a primitive root mod n exactly in the following cases and no others:

  1. n=1, 2, or 4
  2. n=pr where p is an odd prime
  3. n=2pr where p is an odd prime

Read more

  • Jul 31, 2021

Law of Quadratic Reciprocity

Law of Quadratic Reciprocity Let p and q be odd primes. Then

\[ \left( \frac { p } { q } \right) \left( \frac { q } { p } \right) = ( - 1 ) ^ { \frac { p - 1 } { 2 } \frac { q - 1 } { 2 } } \iff \begin{cases} (\frac{p}{q})=(\frac{q}{p}) &\text{if either p or q is }1\bmod 4\\ (\frac{p}{q})=-(\frac{q}{p}) &\text{if both p and q are }3\bmod 4 \end{cases} \]

Note the ring isomorphism \( \mathbb{Z}_{pq}^{*} \cong \mathbb{Z}_{p}^* \times \mathbb{Z}_{q}^* \). Clearly they are also commutative ring, consider the quotient group \( G=\frac{\mathbb{Z}_{p}^* \times \mathbb{Z}_{q}^*}{ U } \) under multiplication, where \( U=\{ (1,1),(-1,-1) \} \). \( |G|=\frac{(p-1)(q-1)}{2} \)

Under \( \mathbb{Z}_{p}^* \times \mathbb{Z}_{q}^* \) :

\[ G=xU \text{ where } x \in X=\{ x_1 \times x_2 = (x_1,x_2) : 1\leq x_1 \leq p-1\ \land 1\leq x_2 \leq \frac{q-1}{2} \} \]

Under \( \mathbb{Z}_{pq}^{*} \) :

\begin{align*} G &= y\{ 1, -1 \} \text{ where } y \in \{ (y,pq)=1 \land 1\leq y \leq \frac{pq-1}{2} \} \\ \iff G &= zU \text{ where } z\in Z=\{ (z_1,z_2) : z_1 \equiv y \bmod p \land z_2 \equiv y \bmod q \} \end{align*}
\begin{align*} \prod_{g\in G} &= ({(p-1)!}^{\frac{q-1}{2}}\ , \ {\frac{q-1}{2}!}^{(p-1)})U\\ &= ((-1)^{\frac{q-1}{2}}\ , \ {\frac{q-1}{2} !}^{2 \cdot \frac{p-1}{2}})U\\ &= ((-1)^{\frac{q-1}{2}}\ , \ (-1)^{\frac{p-1}{2}}\cdot (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}})U\\ &= (\frac{(({pq-1})/{2})!}{\frac{p-1}{2}!\cdot \frac{q-1}{2}!\cdot p^\frac{q -1}{2}\cdot q^\frac{p-1}{2}}\ , \ \frac{(({pq-1})/{2})!}{\frac{p-1}{2}!\cdot \frac{q-1}{2}!\cdot p^\frac{q -1}{2}\cdot q^\frac{p-1}{2}})U \end{align*}

Note:

\begin{align*} &\quad \frac{(({pq-1})/{2})!}{\frac{p-1}{2}!\cdot \frac{q-1}{2}!\cdot p^\frac{q -1}{2}\cdot q^\frac{p-1}{2}}\\ &\equiv \frac{\left( \prod _ { i = 1 } ^ { p - 1 } i \right) \left( \prod _ { i = 1 } ^ { p - 1 } p + i \right) \cdots \left( \prod _ { i = 1 } ^ { p - 1 } \left( \frac { q - 1 } { 2 } - 1 \right) p + i \right) \left( \prod _ { i = 1 } ^ { \frac { p - 1 } { 2 } } \frac { q - 1 } { 2 } p + i \right)}{\frac{p-1}{2}!\cdot q^\frac{p-1}{2}}\\ &\equiv \frac{(-1)^{\frac{q-1}{2}}\cdot \frac{p-1}{2}!}{\frac{p-1}{2}!\cdot q^\frac{p-1}{2}}\\ &\equiv (-1)^{\frac{q-1}{2}}\cdot q^\frac{p-1}{2} \\ &\equiv (-1)^{\frac{q-1}{2}} \cdot (\frac{q}{p}) \mod p \end{align*}
\[ \implies \prod_{g\in G}=((-1)^{\frac{q-1}{2}} \cdot (\frac{q}{p})\ ,\ (-1)^{\frac{p-1}{2}} \cdot (\frac{p}{q}))U \]

\( (a_1,a_2)U=(a_3,a_4)U \implies a_1a_2 \equiv a_3a_4 \mod pq \)

\begin{align*} &\implies (-1)^{\frac{p-1}{2}} \cdot(-1)^{\frac{q-1}{2}} \cdot \left( \frac { p } { q } \right) \left( \frac { q } { p } \right) \equiv (-1)^{\frac{p-1}{2}} \cdot(-1)^{\frac{q-1}{2}} \cdot ( - 1 ) ^ { \frac { p - 1 } { 2 } \frac { q - 1 } { 2 } } \mod pq\\ &\implies \left( \frac { p } { q } \right) \left( \frac { q } { p } \right) = ( - 1 ) ^ { \frac { p - 1 } { 2 } \frac { q - 1 } { 2 } } \end{align*}

Read more

  • Jul 28, 2021

Gauss's lemma

Gauss’s lemma Let p be an odd prime, q be an integer coprime to p. Take the least residues of \( Q=\{q, 2q,\cdots,\frac{p-1}{2} q \} \), i.e. reduce them to integers in \( [0, p-1] \). Let u be the number of members in this set that are greater than p/2. Then

\[ (\frac{q}{p})=-1^u \]

Q has exactly \( \frac{p-1}{2} \) elements since \( (p, q)=1 \) and \( p \) is a prime.We can rewrite Q to integers in \( [-\frac{p-1}{2},\frac{p-1}{2}] \) by rewriting all \( [o_i]_p : o_i>\frac{p-1}{2} \) into \( [-u_i]_p : u_i=p-o_i \land u_i\leq \frac{p-1}{2} \).

\begin{align*} &\implies \prod_{t=1}^{\frac{p-1}{2}}tq\equiv q^{\frac{p-1}{2}}\cdot {\frac{p-1}{2}}!\equiv{\frac{p-1}{2}}! \cdot (-1)^u \mod p \\ &\implies (\frac{q}{p}) \equiv q^{\frac{p-1}{2}} \equiv (-1)^u \mod p \tag*{(By Euler's Criterion)} \end{align*}

Corollary Let p be an odd prime. Then

\begin{equation*} (\frac{2}{p})= \begin{cases} 1 & \text{if } p\equiv1 \lor 7 \mod 8 \\ -1 & \text{if } p\equiv3 \lor 5 \mod 8 \end{cases} \end{equation*}

Because \( 2\cdot\frac{p-1}{2}=p-1<p \), we only need to find out the cut-off point

\[ n:2n\leq\frac{p-1}{2} \land 2(n+1)>\frac{p-1}{2} \implies n=[\frac{p-1}{4}] \implies u=\frac{p-1}{2}-n=\lceil \frac{p-1}{4} \rceil \]
  1. \( p=8k+1 \implies u=\lceil \frac{8k}{4} \rceil=2k \implies (\frac{p-1}{2})=1 \)
  2. \( p=8k+3 \implies u=\lceil \frac{8k+2}{4} \rceil=2k+1 \implies (\frac{p-1}{2})=-1 \)
  3. \( p=8k+5 \implies u=\lceil \frac{8k+4}{4} \rceil=2k+1 \implies (\frac{p-1}{2})=-1 \)
  4. \( p=8k+7 \implies u=\lceil \frac{8k+6}{4} \rceil=2k+2 \implies (\frac{p-1}{2})=1 \)

Read more

  • Jul 26, 2021

Euler's Criterion

Euler’s Criterion Let p be an odd prime, and a an integer not divisible by p. Then

\[ a^{\frac{p-1}{2}}\equiv \frac{a}{p}\mod p \]
  1. \( \frac{a}{p}=1 \), i.e. \( \exists d : d^2 \equiv a \mod p \)
    \[ \implies a^{\frac{p-1}{2}} \equiv d^{p-1} \equiv 1 \mod p \]
  2. \( \frac{a}{p}=-1 \), i.e. \( \forall d : d^2 \not\equiv a \mod p \) since p is a prime, \( \exists g \in (\mathbb Z/p\mathbb Z)^\times:(\mathbb Z/p\mathbb Z)^\times= <g>\implies a=g^{2n+1} \)
    \[ \implies a^{\frac{p-1}{2}} \equiv g^{\frac{(2n+1)(p-1)}{2}}\equiv g^{n(p-1)+\frac{p-1}{2}} \equiv g^\frac{p-1}{2} \mod p \]

    since p is a prime

    \begin{align*} &\implies (g^\frac{p-1}{2})^2 \equiv 1 \mod p \\ &\implies g^\frac{p-1}{2}\equiv1 \mod p \lor g^\frac{p-1}{2}\equiv-1 \mod p \end{align*}

    since g is a generator

    \begin{align*} &\implies g^\frac{p-1}{2}\not\equiv1 \mod p\\ &\implies g^\frac{p-1}{2} \equiv -1 \mod p \end{align*}

Therefore, this theorem is true.

Read more

  • Jul 23, 2021

toccc

First level

second level

thrid

adswadasd

fourth

dadiqwad

Read more

  • Jul 22, 2021

Primitive root theorem

Primitive root theorem Let p be a prime. Then for any d dividing \( p-1 \), there are exactly \( \phi(d) \) elements of order d in \( (\mathbb Z / p \mathbb Z)^\times \). In particular there are \( \phi(p-1) \) primitive roots mod p.

  1. \( H_m \): For any \( d_i \leq m \) dividing \( p-1 \), there are exactly \( \phi(d_i) \) elements of order \( d_i \) in \( (\mathbb Z / p \mathbb Z)^\times \).
  2. \( H_1 \): Only positive divisor of \( p-1 \) less than 1 is 1. \( H_1 \) is obviously true.
  3. \( H_k \): Assume \( H_m \) holds for some positive integer k.
  4. \( H_{k+1} \):
    1. \( k+1 \) doesn’t divide \( p-1 \). Then \( H_{k+1} \) is true since \( H_k \) is true.
    2. \( k+1 \) divides \( p-1 \). Based on \( H_k \), for any \( d_i < k+1 \) dividing \( p-1 \), there are exactly \( \phi(d_i) \) elements of order \( d_i \) in \( (\mathbb Z / p \mathbb Z)^\times \).
\( k+1=d^* \) divides \( p-1 \). \( x^{d^*}=1 \) has \( d^* \) distinct roots mod p. Clearly the order of the roots must divide \( d^* \).
      \begin{equation} d^{*}-\sum_{q | d^{*}, q<d^*} \phi(q)=\phi(d^{*}) \end{equation}

      So there are exactly \( \phi(k+1) \) elements of order \( k+1 \) in \( (\mathbb Z / p \mathbb Z)^\times \).

    Overall, \( H_{k+1} \) is true.

  5. Based on M.I., \( H_m \) is true.

Read more

  • Jul 22, 2021
Search