Determine the smallest non-negative integer a that satisfies the congruences:
a == 2 mod 3,
a == 4 mod 5,
a == 6 mod 7
a == 8 mod 9
+26396 Determine the smallest non-negative integer a that satisfies the congruences:
a == 2 mod 3,
a == 4 mod 5,
a == 6 mod 7
a == 8 mod 9
1.
\(\begin{array}{|rcll|} \hline & \mathbf{ a } & \mathbf{\equiv}& \mathbf{8 \pmod{9}} \\\\ \text{or} & a &=& 8+9n \\ & a &=& 8 + 3\cdot 3n \\ \text{or} & a &\equiv & 8 \pmod{3} \quad & | \quad 8 &\equiv & 2 \pmod{3}\\\\ & \mathbf{ a } & \mathbf{\equiv}& \mathbf{2 \pmod{3}} \\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline (1) & \mathbf{ a } & \mathbf{\equiv}& \mathbf{4 \pmod{5}} \\ (2) & \mathbf{ a } & \mathbf{\equiv}& \mathbf{6 \pmod{7}} \\ (3) & \mathbf{ a } & \mathbf{\equiv}& \mathbf{8 \pmod{9}} \quad & | \quad \text{implicit } a \equiv 2 \pmod{3} \\ \hline \end{array}\)
Solve:
\(\begin{array}{|rcll|} \hline a &=& 4\cdot 7 \cdot 9 \cdot \frac{1}{7 \cdot 9}\pmod{5} \\ &+& 6\cdot 5 \cdot 9 \cdot \frac{1}{5 \cdot 9}\pmod{7} \\ &+& 8\cdot 5 \cdot 7 \cdot \frac{1}{5 \cdot 7}\pmod{9} \\ &+& 5\cdot 7 \cdot 9 n \qquad n\in Z \\\\ a &=& 252 \cdot \left( 63^{-1} \pmod{5} \right) \\ &+& 270 \cdot \left( 45^{-1} \pmod{7} \right) \\ &+& 280 \cdot \left( 35^{-1} \pmod{9} \right) \\ &+& 315 n \\\\ a &=& 252 \cdot \left( 63^{\phi(5)-1} \pmod{5} \right) \quad &|\quad \gcd(63,5) = 1,\ \phi(5) = 5-1=4 \\ &+& 270 \cdot \left( 45^{\phi(7)-1} \pmod{7} \right) \quad &|\quad \gcd(45,7) = 1,\ \phi(7) = 7-1=6 \\ &+& 280 \cdot \left( 35^{\phi(9)-1} \pmod{9} \right) \quad &|\quad \gcd(35,9) = 1,\ \phi(9) = 9(1-\frac13)=6 \\ &+& 315 n \\\\ a &=& 252 \cdot \left( 63^{4-1} \pmod{5} \right) \quad &|\quad \gcd(63,5) = 1,\ \phi(5) = 5-1=4 \\ &+& 270 \cdot \left( 45^{6-1} \pmod{7} \right) \quad &|\quad \gcd(45,7) = 1,\ \phi(7) = 7-1=6 \\ &+& 280 \cdot \left( 35^{6-1} \pmod{9} \right) \quad &|\quad \gcd(35,9) = 1,\ \phi(9) = 9(1-\frac13)=6 \\ &+& 315 n \\\\ a &=& 252 \cdot \left( 63^{3} \pmod{5} \right) \quad &|\quad 63^{3} \pmod{5} = 2 \pmod{5} \\ &+& 270 \cdot \left( 45^{5} \pmod{7} \right) \quad &|\quad 45^{5} \pmod{7} = 5 \pmod{7} \\ &+& 280 \cdot \left( 35^{5} \pmod{9} \right) \quad &|\quad 35^{5} \pmod{9} = 8 \pmod{9} \\ &+& 315 n \\\\ a &=& 252 \cdot 2 + 270 \cdot 5 + 280 \cdot 8 + 315 n \\ a &=& 4096 + 315 n \quad &|\quad 4096 \equiv 314 \pmod{315} \\ \mathbf{a} & \mathbf{=}&\mathbf{ 314 + 315 n \qquad n\in Z }\\ \hline \end{array}\)
The smallest non-negative integer a is 314
A * 9 + 8 =B * 7 + 6=C * 5 + 4=D * 3 + 2, solve for A, B, C, D
A=34, B =44, C=62, D=104
9*34 + 8 =314 - The smallest positive integer
The LCM{3, 5, 7, 9} =315
315n + 314, where n =0, 1, 2, 3........etc.
