Number Theory

If a = 8 (mod 9), then a must be 2 (mod 3), so we can forget about that equation. 

a = 4 (mod 5)

a = 1 (mod 7)

a = 8 (mod 9)

I'm going to use the Chinese Remainder Theorem, which is a bit difficult to exaplain, but there are some good videos on youtube. 

Starting with mod 5. 

x = 0 (mod 7) and (mod 9) but 4 (mod 5). 

x = 7*9*n = 4 (mod 5)

This works when n = 3, x = 189. 

Then, mod 7. 

x = 0 (mod 5) and (mod 9) but 1 (mod 7). 

x = 5*9*n = 1 (mod 7).

This works when n = 5, x = 225. 

Then, mod 9. 

x = 0 (mod 5) and (mod 7) but 8 (mod 9). 

x = 5*7*n = 8 (mod 9).

This works when n = 1, x = 35. 

Finally, we add everything up. 

189 + 225 + 35 = 449

We can make it smaller by doing 449 - 5*7*9 = 134. 

=^._.^=

Determine the smallest non-negative integer a that satisfies the congruences:

$a \equiv 2 \pmod{ 3}\\ a \equiv 4 \pmod{ 5}\\ a \equiv 1 \pmod{ 7}\\ a \equiv 8 \pmod{ 9}$

1. join
$a \equiv 2 \pmod{ 3} \\ a \equiv 8 \pmod{ 9}$

$\begin{array}{|rcll|} \hline a&=&2+3n \\ a&=&8+9m \\ \hline 2+3n&=& 8+9m \\ 3n&=& 6+9m \quad | \quad : 3\\ n&=& 2+3m \\ \hline a&=&2+3n \quad | \quad n=2+3m \\ a&=&2+3(2+3m) \\ a&=&2+6+9m \\ a&=&8+9m \\ \mathbf{a} \equiv \mathbf{ 8 \pmod{ 9} } \\ \hline \end{array} \\ \begin{equation}\left . \begin{aligned} & a \equiv 2 \pmod{ 3} \\ & a \equiv 8 \pmod{ 9} \end{aligned}\right \rbrace \mathbf{a} \equiv \mathbf{ 8 \pmod{ 9} } \end{equation}$

2. join
$a \equiv 4 \pmod{ 5} \\ a \equiv 1 \pmod{ 7}$

$\begin{array}{|rcl|rcl|rcl|} \hline a&=&4+5r \\ a&=&1+7s \\ \hline 4+5r&=&1+7s \\ 5r &=& 7s-3 \\ r &=& \frac{7s-3}{5} \\ r &=& \frac{5s+2s-3}{5} \\ r &=& s+ \underbrace{ \frac{2s-3}{5} }_{=t} \\ \mathbf{r} &=& \mathbf{s+t} & t &=& \frac{2s-3}{5}\\ & & & 5t &=& 2s-3 \\ & & & 2s &=& 5t+3 \\ & & & s&=& \frac{5t+3}{2} \\ & & & s&=& \frac{4t+t+2+1}{2} \\ & & & s&=& 2t+1 + \underbrace{ \frac{t+1}{2}}_{=u} \\ & & & \mathbf{s}&=& \mathbf{2t+1 + u} \\ & & & & & & u&=&\frac{t+1}{2} \\ & & & & & & 2u&=& t+1 \\ & & & & & & t&=& 2u-1 \\ & & & s &=& 2(2u-1)+1 +u \\ & & & s &=& 5u-1 \\ r &= &5u-1+2u-1 \\ r &= &7u-2 \\ \hline a &=& 4+5r \\ a &=& 4+5(7u-2) \\ a &=& -6+35u \\ \mathbf{a} &\equiv& \mathbf{ -6 \pmod{ 35} } \\ \hline \end{array}\\ \begin{equation}\left . \begin{aligned} & a \equiv 4 \pmod{ 5} \\ & a \equiv 1 \pmod{ 7} \end{aligned}\right \rbrace \mathbf{a} \equiv \mathbf{ -6 \pmod{ 35} } \end{equation}$

3. join
$a \equiv 8 \pmod{ 9} \\ a \equiv -6 \pmod{35}$

$\begin{array}{|rcl|rcl|rcl|} \hline a&=&8+9v \\ a&=&-6+35w \\ \hline 8+9v&=&-6+35w \\ 9v &=& 35w-14 \\ v&=& \frac{35w-14}{9} \\ v &=& \frac{27w+8w-9-5}{9} \\ v &=& 3w-1+ \underbrace{ \frac{8w-5}{9} }_{=x} \\ \mathbf{v} &=& \mathbf{3w-1+x} & x &=& \frac{8w-5}{9}\\ & & & 9x &=& 8w-5 \\ & & & 8w &=& 9x+5 \\ & & & w&=& \frac{9x+5}{8} \\ & & & w&=& \frac{8x+x+5}{8} \\ & & & w&=& x + \underbrace{ \frac{x+5}{8}}_{=y} \\ & & & \mathbf{w}&=& \mathbf{x+y} \\ & & & & & & y&=&\frac{x+5}{8} \\ & & & & & & 8y&=& x+5 \\ & & & & & & x&=& 8y-5 \\ & & & w &=& 8y-5 +y \\ & & & w &=& 9y-5 \\ v &= &3(9y-5)-1+8y-5 \\ v &= &35y-21 \\ \hline a &=& 8+9v \\ a &=& 8+9(35y-21) \\ a &=& -181+315y \\ \mathbf{a} &\equiv& \mathbf{ -181 \pmod{ 315} } \\ \mathbf{a} &\equiv& \mathbf{ -181+315 \pmod{ 315} } \\ \mathbf{a} &\equiv& \mathbf{ 134 \pmod{ 315} } \\ \hline \end{array}\\ \begin{equation}\left . \begin{aligned} & a \equiv 8 \pmod{ 9} \\ & a \equiv -6 \pmod{35} \end{aligned}\right \rbrace \mathbf{a} \equiv \mathbf{ 134 \pmod{ 315} } \end{equation}$

The smallest non-negative integer a is 134