Home

Proposition

If

1. \( \forall s \in S, s\in A_1 \cup A_2 \, \land \, A_1 \cup A_2 = \varnothing \)
2. \( s\in A_1 \implies s \in B_1 \, \land \, s\in A_2 \implies s \in B_2 \)
3. \( \forall s \in S, s\in B_1 \cup B_2 \, \land \, B_1 \cup B_2 = \varnothing \)

Then \( \forall s \in S, s\in B_1 \implies s \in A_1 \, \land \, s\in B_2 \implies s \in A_2 \)

\( (s\in A_2 \implies s \in B_2) \iff \{ \lnot (s \in B_2) \implies \lnot (s\in A_2) \} \)

Since \( B_1, B_2 \) partition \( S \), \( s \not\in B_2 \iff s\in B_1 \). Similarly, \( s \not\in A_2 \iff s\in A_1 \)

Thus, \( (s\in A_2 \implies s \in B_2) \iff (s\in B_1 \implies s \in A_1) \)

Similarly, \( (s\in A_1 \implies s \in B_1) \iff (s\in B_2 \implies s \in A_2) \)

Corollary

If

1. \( \forall s \in S, s\in A_1 \cup A_2 \cup \cdots \cup A_n \, \land \, A_1,A_2,\ldots,A_n \) are pairwise disjoint
2. \( s\in A_i \implies s \in B_i \)
3. \( \forall s \in S, s\in B_1 \cup B_2 \cup \cdots \cup B_n \, \land \, B_1,B_2,\ldots,B_n \) are pairwise disjoint

Then \( \forall s \in S, s\in B_i \implies s \in A_i \)

Proposition Suppose there exists a nontrivial element of \( \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \). Then every element of \( \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \) is of the form \( \pm \epsilon ^ { n } \) for some \( n \) in \( \mathbb { Z } \), where \( \epsilon \) is the fundamental 1-unit.

Assume there exists a nontrivial element of \( \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \), \( t \). \( \forall n \in \mathbb {Z}, t \neq \pm \epsilon ^ { n } \). Then \( \exists k \in \mathbb { Z } : t \in (\epsilon^k,\epsilon^{k+1}) \, \lor \, -t \in (\epsilon^k,\epsilon^{k+1}) \).

If \( t \in (\epsilon^k,\epsilon^{k+1}) \), \( t\cdot \epsilon^{-k} \in \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \). \( t<\epsilon^{k+1} \implies 1=\epsilon^{0}<t\cdot \epsilon^{-k} < \epsilon \). Since \( t \neq \pm \epsilon ^ { n } \), \( t\cdot \epsilon^{-k} \) is a nontrivial element of \( \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \). Contradiction, such \( t \) must not exist.

Similarly, if \( -t \in (\epsilon^k,\epsilon^{k+1}) \), such \( t \) must not exist due to contradiction.

Thus, every element of \( \mathbb { Z } [ \sqrt { d } ] ^ { \times , 1 } \) is of the form \( \pm \epsilon ^ { n } \) for some \( n \) in \( \mathbb { Z } \), where \( \epsilon \) is the fundamental 1-unit.

Proposition If \( \alpha \) is an algebraic integer of degree two, then \( \mathbb Z [\alpha] \) is equal to the set of complex numbers of the form \( x + y\alpha \), where x and y are integers.

Theorem Suppose that unique factorization holds in \( \mathbb { Z } [ \alpha ] \), and let p be an integer prime such that the polynomial \( P ( x , 1 ) = x ^ { 2 } - b x + c \) has a root mod p. Then there exist integers x and y such that \( P (x, y) = p \). Conversely, if there exist such x and y, then \( x^2 - bx + c \) has a root mod p.

\( \Rightarrow \):
• \( \exists x \in \mathbb Z : p \mid x ^ { 2 } - b x + c = (x+\alpha)(x-\alpha) \) but \( p \nmid (x+\alpha)\, \lor \,(x-\alpha) \). So \( p \) is not a prime in \( \mathbb { Z } [ \alpha ] \). \( N(p)=p^2 \implies \exists q = q_1+ q_2 \alpha \in \mathbb { Z } [ \alpha ] : q|p \land N(q)=P(q_1,q_2)=p \)
\( \Leftarrow \):
• Assume \( y \) has an inverse \( y^{-1} \) mod \( p \). Then
  \[ P (x, y)\cdot (y^{-1})^2 \equiv (xy^{-1})^2 -b(xy^{-1}) + c\equiv p \equiv 0 \equiv P ((xy^{-1}), 1) \mod p \]

  • Claim 1 y must have an inverse \( y^{-1} \) mod \( p \).

    Assume \( y \) does not have an inverse. Since \( p \) is a prime \( y \equiv 0 \mod p \). \( P(x,y)\equiv x^2 \equiv 0 \mod p \implies p|x^2 \implies p^2|x^2 \implies P(x,y)\equiv 0 \mod p^2 \). But \( P(x,y)\equiv p \not\equiv 0 \mod p^2 \)

    Contradiction, so \( y \) must have an inverse.

Lemma 1 Let p be an odd prime. The polynomial \( x^2- bx + c \) has a root mod p if, and only if, \( b^2- 4c \) is zero or a quadratic residue mod p.

\( \Rightarrow \):
• \( \exists x \in \mathbb Z : x^2- bx + c \equiv (2x-b)^2+(4c-b^2) \equiv 0 \mod p \)

  \( \implies (2x-b)^2 \equiv b^2- 4c \mod p \)

  \( \implies b^2- 4c \) is zero or a quadratic residue mod p

\( \Leftarrow \):
• Since \( p \) is a prime, there exists a primitive root \( r \bmod p \)

  \( \implies b^2- 4c \equiv r^{2n} \mod p \)

  \[ \text{Set }x=\begin{cases} (r^n+b+p)/2 & \text{if } r^n+b \equiv 1 \bmod 2\\ (r^n+b)/2 & \text{if } r^n+b \equiv 0 \bmod 2 \end{cases} \]

  \( \implies 2x - b \equiv r^{n} \mod p \)

  \( \implies (2x-b)^2+(4c-b^2) \equiv 4 \cdot (x^2- bx + c) \equiv 0 \mod p \)

  \( \implies x^2- bx + c \equiv 0 \mod p \)

Assume \( p \) is an integer prime that is congruent to \( 1\bmod 4 \). Then \( \exists n,r \in \mathbb Z : n^2+1=pr \implies p|(n+i)(n-i) \) Note \( p \) does not divide either \( n+i \) or \( n-i \). So \( p \) is not a prime in \( \mathbb Z [i] \). Then there exists a prime \( q \in \mathbb Z [i] : q|p \).

\( \implies N(q)|N(p)=p^2 \) since \( p,q \) are not associates \( \implies N(q)=N(q_1+q_2 i)=q_1^2+q_2^2=p \) where \( q_1, q_2 \) are integers

Note we can find \( q=\gcd(p,n+i) \) by Euclid’s algorithm.

Proposition (Prime in \( {\mathbb Z [i] } \)) Primes in \( {\mathbb Z [i] } \) are either of the form a +bi, where \( a^2 +b^2 \) is an integer prime, or, q and its associate, where q is an integer prime that is not the sum of two squares.

Lemma Let p be a prime in \( {\mathbb Z [i] } \). Then there exists an integer prime q such that either \( N (p) = q \) or \( N (p) = q^2 \). In the latter case p is an associate of q. Moreover, \( N (p) = q \) if and only if q is the sum of two squares.

\( N(p) \in \mathbb{Z}^* \implies p \overline {p} = N(p)=q_1q_2\cdots q_m \) where \( q_i \) are integer primes.

Note \( q_i \in {\mathbb Z [i] } \implies \exists q_s : p \mid q_s \implies \exists t \in {\mathbb Z [i] } : pt=q_s \implies N(p) N(t)= N(q_s) \)

\( \implies N(p) \mid q_s^2 \implies N(p)= q_s \, \lor \, q_s^2 \)

• Claim 1 If \( N (p) = q^2 \), then p is an associate of q.

  \( N(p) N(t)= N(q)=q^2 \implies N(t)=1 \implies t \) is a unit

  \( \implies pu=q \implies \) \( p \) is an associate of \( q \)

• Claim 2 \( N (p) = q \) if and only if q is the sum of two squares.

  \( \Rightarrow \):
  • \( N (p) = N(a+bi)=a^2+b^2=p \)
  \( \Leftarrow \):
  • Assume \( p \) is a prime in \( {\mathbb Z [i] } \) and \( N (p) = q^2 \). Based on Claim 1, \( q \) is an associate of \( p \). Thus, \( q \) is a prime in \( {\mathbb Z [i] } \).

    Note \( \exists a,b \in \mathbb Z : a^2+b^2=p \implies \exists r=a+bi \in {\mathbb Z [i] } : r\overline {r}=p \) \( \implies q \) is not a prime in \( {\mathbb Z [i] } \). Contradiction, \( N(p) \) must be \( q \)

Proposition a is a primitive root modulo n then it is also a primitive root modulo d, for any d dividing n.

Claim: The map \( \mathbb{Z}_{n}^{*} \rightarrow \mathbb{Z}_{d}^* \) is surjective. \( d=\prod p_i^{r_{di}} , \ n=\prod p_i^{r_{fi}} \cdot \prod q_i^{r_{gi}} \) where \( p_i, q_i \) are all distinct prime. Set \( f=\prod p_i^{r_{fi}} , \ g=\prod q_i^{r_{gi}} \) then \( n=fg \).

Note \( (d,g)=1 \implies \exists x \in \mathbb{N} : xd\equiv 1 \bmod g \). For any \( [i]_g \in \mathbb{Z}_{d}^* \), \( i\equiv u \bmod g \) where \( u\in [0, g-1] \).

\( (g-u+1)x \equiv k \mod g \) where \( k \in [0, g-1] \). \( \implies i+kd\equiv 1 \mod g \implies (i+kd,g)=1 \). \( \forall p_i : p_i \mid f \), \( p_i \nmid (i+kd) \) since \( (i, p_i)=1 \land pi\mid kd \).

Since \( \mathbb{Z}_{n}^{*}=<[a]_n> \) and the map \( \mathbb{Z}_{n}^{*} \rightarrow \mathbb{Z}_{d}^* \) is surjective.

Therefore, a is a primitive root modulo d.