+0  
 
0
151
3
avatar

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

Guest Aug 3, 2018
 #1
avatar
0

a =314

Guest Aug 3, 2018
 #2
avatar+20680 
0

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

 

laugh

heureka  Aug 3, 2018
 #3
avatar
0

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.

Guest Aug 3, 2018
edited by Guest  Aug 3, 2018
edited by Guest  Aug 3, 2018
edited by Guest  Aug 3, 2018
edited by Guest  Aug 3, 2018

11 Online Users

avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.