Home

Proposition 1 \( a,b \) are non-zero element of an integral domain \( R \). \( a \) divides \( b \) and \( b \) divides \( a \) if and only if there exist a unit \( u \) such that \( a=bu \)

\( \Rightarrow: \)
• \( \exists r,s \in R : sa=b \) and \( rb=a \). Then, \( a=rsa \) and \( a(1-rs)=0 \). Since \( R \) is an integral domain and \( a \) is non-zero, \( 1-rs=0 \). Thus, \( r,s \) are units and \( a=rb \).
\( \Leftarrow: \)
• \( a=bu \implies b \mid a \). Since \( u \) is a unit, \( \exists t \in R : ut=1 \). \( at=b(ut)=b \implies a \mid b \).

Proposition 2 \( a|b \iff \langle b \rangle \subseteq \langle a \rangle \)

Corollary 2.1 \( a,b \) are associates \( \iff \langle a \rangle = \langle b \rangle \)

Proposition 3 \( p \) is irreducible if and only if \( \langle p \rangle \) is maximal amongst all principal ideals that contain \( \langle p \rangle \).

\( \Rightarrow: \)
• For any principal ideal \( \langle x \rangle \) that contains \( \langle p \rangle \) and is not the unit ideal, \( p \in \langle x \rangle \). So there exists \( r \in R : p=xr \). Since \( x \) divides \( p \) and \( p \) is irreducible, \( x \) is either an unit or an associate of \( p \). If \( x \) is an unit, then \( \langle x \rangle \) is the unit ideal. Thus, \( x \) is an associate of \( p \). Based on the previous corollary, \( \langle x \rangle = \langle p \rangle \) and \( \langle p \rangle \) is maximal amongst all principal ideals that contain \( \langle p \rangle \).
\( \Leftarrow: \)
• For any \( r \) that divides \( p \), \( \langle p \rangle \subseteq \langle r \rangle \). Since \( \langle p \rangle \) is maximal amongst all principal ideals, \( \langle p \rangle = \langle r \rangle \) or \( \langle r \rangle \) is the unit ideal. So, \( r \) is either an associate of \( p \) or an unit. Thus, \( p \) is irreducible.

Proposition 4 In an integral domain \( R \), every prime is irreducible.

\( p \) is a prime in an integral domain \( R \). For any \( a,b \in R \) such that \( p=ab \). Since \( p \) is a prime, WLOG, let’s assume \( p|a \). Then there exist \( t \in R \) such that \( pt=abt=a \). So, \( a(bt-1)=0 \). Since \( R \) is an integral domain and \( a\neq 0 \), \( bt=1 \) and \( b \) is an unit. Therefore, \( a \) is an associate of \( p \) and \( p \) is irreducible.

Definition 1 An ideal \( I \) of \( R \) is prime if the quotient \( R / I \) is an integral domain. It is maximal if \( R / I \) is a field.

Lemma 2 An ideal \( I \) is prime if, and only if, for every pair of elements \( r , s \) in \( R \) such that \( rs \) is in \( I \), either \( r \) is in \( I \) or s is in \( I \).

\( \Rightarrow: \)
• An ideal \( I \) of \( R \) is prime \( \implies \) \( R / I \) is an integral domain \( \implies \forall a,b \in R/I, ab=0+I \implies a=0+I \lor b=0+I \)

  Since \( \forall a,b \in R/I, \exists x,y \in R : a=x+I,b=y+I \). So, \( ab=xy+I=0+I \implies x+I=0+I \lor y+I=0+I \). Thus, \( \forall xy-0 \in I \implies x-0=x \in I \lor y \in I \).

\( \Leftarrow: \)
• \( xy \in I \implies x \in I \lor y \in I \)

  \( \forall x+I,y+I \in R/I, (x+I)(y+I)=xy+I=0+I \implies xy \in I \implies x+I=0+I \lor y+I =0+I \). Thus, \( R / I \) is an integral domain and \( I \) is prime.

Lemma 3 The only ideals of a field are the zero ideal and the unit ideal.

Assume \( I \) is an ideal of the field \( F \) that has a non-zero element \( r \). By definition, \( \exists r^{-1} \in F : rr^{-1}=1\in I \). Since \( 1 \in I \), unit ideal must be a subset of \( I \). But every ideal is a subset of the unit ideal, so \( I \) must be equivalent to the unit ideal.

Clearly, zero ideal is also an ideal of \( F \).

Lemma 4 An ideal \( I \) is maximal if, and only if, the only ideals of \( R \) containing \( I \) are \( I \) and the unit ideal.

\( \Rightarrow: \)
• \( I \) is maximal \( \implies \) \( R / I \) is a field

  Assume there exist an ideal \( J \) of \( R \) such that \( I \subseteq J \subseteq R \). Note \( J/I \subseteq R/I \). Since \( J \) is an ideal of R, \( J/I \) is an ideal of \( R/I \). \( R / I \) is a field. Based on the previous lemma, \( J/I \) is zero ideal or unit ideal which means \( J=I \) or \( J=R. \)

\( \Leftarrow: \)
• For any \( r \in R \setminus I \), \( I \) is an ideal of \( I+\langle r \rangle \). \( r \not\in I \), \( I+\langle r \rangle \) must be the unit ideal. Thus, \( 1 \in (I+\langle r \rangle) \). There exists \( t \in R, i \in I : i+rt=1 \). Thus, \( rt \equiv 1 \bmod I \) and \( r \) has an inverse in \( R/I \). Note, \( \forall i \in I, i\equiv 0 \bmod I \). Therefore, \( R / I \) is a field.

Proposition If \( I + J = \langle 1 \rangle \), then \( I \cap J = I J \)

Third Isomorphism Theorem for Groups Let \( G \) be a group and let \( H \) and \( K \) be normal subgroups of \( G \), with \( H \leq K \). Then

1. \( K / H \unlhd G / H \)
2. \( ( G / H ) / ( K / H ) \cong G / K \)

1. \( \forall x \in K/H; y \in G/H, \exists k \in K; g \in G : x=kH; y=gH \) and \( yxy^{-1}=(gkg^{-1})H \). Since \( K \) is a normal subgroup of \( G \), \( gkg^{-1} \in K \). Thus, \( yxy^{-1} \in K/H \) and \( K / H \unlhd G / H \)
2. Consider a mapping \( \phi : G/H \rightarrow G/K \) by \( \phi(gH)=gK \)

   The map is well-defined since if \( aH=bH \), then \( a^{-1}b\in H \subseteq K \) and

   \[ \phi(aH)=aK \circ (a^{-1}b) K = bK=\phi(bH) \]

   The map is homomorphic since \( \forall aH, bH \in G/H \),

   \[ \phi(aH)\phi(bH)=(aK)(bK)=(ab)K=\phi((ab)H) \]

   It is easy to tell \( \phi \) is surjective, so \( \operatorname { im } ( \phi )=G/K \).

   \[ \phi(gH)=gK=K \iff g\in K \iff gH \in K/H \implies \operatorname { ker } ( \phi )=K/H \]

   Based on First Isomorphism Theorem, \( ( G / H ) / ( K / H ) \cong G / K \)

Second Isomorphism Theorem for Groups Let \( G \) be a group, \( H \leq G \) and \( N \unlhd G \). Then

1. \( HN \leq G \)
2. \( H \cap N \unlhd H \)
3. \( HN / N \cong H / ( H \cap N ) \)

1. \( N \unlhd G \implies HN=NH \implies HN \leq G \)
2. \( \forall x \in H \cap N, x \in H \land x \in N. \) Since \( N \unlhd G \), \( \forall x \in H \cap N; h \in H, hxh^{-1} \in N \). Note, \( x,h,h^{-1} \in H \). So, \( hxh^{-1} \in H \). Thus, \( hxh^{-1} \in H \cap N \) and \( H \cap N \unlhd H \).
3. Consider now the canonical homomorphism \( \varphi : HN \longrightarrow HN / N \) by \( \varphi(h_in)=h_iN \)

   The restriction of \( \varphi \) to \( H \) is a homomorphism of \( H \) in \( HN / N \) with kernel: \( H \cap \operatorname { ker } ( \varphi )=H \cap N \). It is not difficult to see that \( \operatorname { im } ( \varphi_{H} )=HN/N \). Based on First Isomorphism Theorem, \( H / ( H \cap N ) \cong HN / N \)

First Isomorphism Theorem for Groups If \( \phi : G \rightarrow H \) is a homomorphism then

Define a mapping \( f:G / \operatorname { ker } ( \phi ) \rightarrow \operatorname { im } ( \phi ) \) by \( f(a\operatorname { ker } ( \phi ))= \phi (a) \)

The map is well-defined since if \( a\operatorname { ker } ( \phi )=b\operatorname { ker } ( \phi ) \), then \( a^{-1}b \in \operatorname { ker } ( \phi ) \) and

Let \( h \) be an arbitrary element of \( \operatorname { im } ( \phi ) \), then \( \exists g \in G : \phi(g)=h \). Since \( f(g\operatorname { ker } ( \phi ))=\phi(g)=h \), \( f:G / \operatorname { ker } ( \phi ) \rightarrow \operatorname { im } ( \phi ) \) is surjective. It is also injective because \( f(a\operatorname { ker } ( \phi ))=f(b\operatorname { ker } ( \phi )) \implies \phi(a)=\phi(b) \implies \phi(a)\phi(b^{-1})=e_H \implies ab^{-1}\in \operatorname { ker } ( \phi ) \implies a\operatorname { ker } ( \phi )=b\operatorname { ker } ( \phi ) \)

\( f:G / \operatorname { ker } ( \phi ) \rightarrow \operatorname { im } ( \phi ) \) is a homomorphism since

Proposition Suppose that \( \alpha \) has an eventually periodic continued fraction expansion. Then \( \alpha \) is a quadratic irrational.

We first show this when \( \alpha \) has a periodic continued fraction expansion. We then have a \( d \) such that

Since \( \alpha_0,\alpha_1, \cdots, \alpha_{d-1} \) are all integers

Since \( \alpha \) is irrational, \( z \neq 0 \). Thus, \( \alpha \) is a quadratic irrational.

If \( \alpha=[\alpha_0,\alpha_1,\ldots,\alpha_m,\alpha_{m+1},\ldots,\alpha_{m+d-1},\alpha_{m+d},\ldots] \), then

Clearly \( \beta \) has a periodic continued fraction expansion. So it is quadratic irrational.

Note,

Since \( \alpha \) is irrational, \( a' \neq 0 \). Thus, \( \alpha \) is a quadratic irrational.

Liouville’s theorem on diophantine approximation Let \( \alpha \) be an irrational number that is algebraic of degree \( d \). Then for any real number \( e > d \), there are at most finitely many rational numbers \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \).

If there is no such rational number \( \frac { { p } } { q } \) then the number of solution is clearly finite.

Now assume there exists at least one rational number \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \).

Let \( P(x) \) be a polynomial of degree \( d \), with integers coefficients, such that \( P(\alpha)=0 \). Choose \( \epsilon \) such that \( P(x) \) has no roots other that \( \alpha \) on the interval \( [\alpha - \epsilon, \alpha + \epsilon] \)

Write \( P(x)=(x-\alpha) \cdot Q(x) \) where \( Q(x) \) is a monic polynomial with real coefficients of degree \( d-1 \). Since \( Q(x) \) is continuous, there exists \( K>0 \) such that \( |Q(x)| \leq K \) on the interval \( [\alpha - \epsilon, \alpha + \epsilon] \)

For all rational number \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \), \( \left| \frac { p } { q } - \alpha \right|>\epsilon \) or \( \left| \frac { p } { q } - \alpha \right| \leq \epsilon \)

For all rational number \( \frac { { p } } { q } \) such that \( \epsilon < \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \). \( q^e< 1/\epsilon \) and \( p \in [q(\alpha - \frac { 1 } { q ^ { e } }), q(\alpha + \frac { 1 } { q ^ { e } })] \), it is not difficult to tell the number of such rational numbers will be finite.

For all rational number \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \, \land \, \left| \frac { p } { q } - \alpha \right| \leq \epsilon \). Note

Since \( P \) has degree \( d \) and integer coefficients,

where both the nominator and the denominator are integers. Since \( \alpha \) is irrational, \( P ( \frac { p } { q } ) \neq 0 \). Then \( \left| P \left( \frac { p } { q } \right) \right| \geq \frac { 1 } { q ^ { d } } \). Note

Similarly, the number of rational numbers \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \, \land \, \left| \frac { p } { q } - \alpha \right| \leq \epsilon \) will be finite.

Therefore, there are at most finitely many rational numbers \( \frac { { p } } { q } \) such that \( \left| \frac { p } { q } - \alpha \right| < \frac { 1 } { q ^ { e } } \).

Theorem 1 Let \( \alpha \) be an irrational number, and \( Q > 1 \) an integer. Then there exist \( p , q \) integers, with \( 1 \leq q < Q \), such that \( | p - q \alpha | < \frac { 1 } { Q } \).

For \( 1\leq k \leq Q-1 \): Set \( \alpha_{k}=\left\lfloor k\alpha \right\rfloor \) such that \( 0 < k\alpha - \alpha_{k} < 1. \)

Partition the interval \( [0,1] \) into \( [0,1/Q] \cup [1/Q, 2/Q] \cup \cdots \cup [(Q-1)/Q, 1] \). So there are in total \( Q \) subintervals. Let \( S=\{0, \alpha - \alpha_{1}, 2\alpha - \alpha_{2}, \ldots (Q-1)\alpha - \alpha_{Q-1} ,1\} \), \( |S|=Q+1 \). There there must be a subinterval from earlier which contains at least 2 elements of \( S \) which are not 0 and 1. Set \( \alpha_0=0, \alpha_Q=1 \). Since \( s_x \) and \( s_y \) are in the same subinterval, \( |s_x-s_y|=|m\alpha-(\alpha_y-\alpha_x)| < 1/Q \) where \( 1 \leq m < Q \).

Corollary 2 For any irrational \( \alpha \) there are infinitely many \( \frac { p } { q } \) such that

For any given \( Q\in Z \) there exists integers \( p, q \) that satisfies the above ineqaulity. Find \( Q' \in \mathbb Z : \frac 1 Q' < | p- q\alpha | \). Then there exists integers \( p' , q' \) such that \( | p'- q'\alpha | < \frac 1 Q' < | p- q\alpha | \). Clearly \( p \neq p' \, \land \, q \neq q' \). We can repeat this process to find infinitely many such \( p, q \).

Theorem 3 For any squarefree d there is a nontrivial solution to \( x^2 - d y^2=1 \)

Since we are looking for nontrivial solution \( y\neq 0 \). \( x^2 - d y^2=1 \iff \frac x y = \sqrt d \). Based on the earlier corollary, there are infinitely many \( \frac { x } { y } \) such that

Note

Therefore,

Since \( N(x + y\sqrt d) \in \mathbb Z \) and is bounded in a finite interval, there exists an integer \( M : |M|<3\sqrt d \, \land \, \)there exists infinitely many pairs of \( (x,y) \) such that \( N(x + y\sqrt d) = M \).

Since there are finitely many congruence classes mod \( M \), there are infinitely many \( x \) in at least one congruence classes \( [x_0]_M \). And there are infinitely many \( y \) that is paired up with such \( x \) in at least one congruence classes \( [y_0]_M \).

For any \( (x_i, y_i) \) and \( (x_j, y_j) \) that satisfy the above conditions,

Note,

Therefore, \( \exists a,b \in \mathbb Z \) s.t.

It is easy to tell that \( N(a+b\sqrt { d })=M/M =1 \). The solution is nontrivial when \( (x_i, y_i) \neq (x_j, y_j) \).