We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
219
1
avatar

What is the residue modulo 16 of the sum of the modulo 16 inverses of the first 8 positive odd integers? Express your answer as an integer from 0 to 15, inclusive.

 Jul 29, 2018
 #1
avatar+21991 
0

What is the residue modulo 16 of the sum of the modulo 16 inverses of the first 8 positive odd integers?

Express your answer as an integer from 0 to 15, inclusive.

 

\(\begin{array}{|lrcl|} \hline \gcd(1,16)=\gcd(3,16)=\gcd(5,16)=\gcd(7,16) \\ =\gcd(9,16)=\gcd(11,16)=\gcd(13,16)=\gcd(15,16)=1 \\\\ \begin{array}{|rcl|} \hline \phi(16)&=& 16\cdot\left(1-\dfrac12 \right) \\ &=& 8 \\ \hline \end{array} \\ \hline \end{array} \)

 

 

\(\begin{array}{|rcll|} \hline && \Big( 1^{-1} \pmod {16} + 3^{-1} \pmod {16} + 5^{-1} \pmod {16} \\ && + 7^{-1} \pmod {16} + 9^{-1} \pmod {16} + 11^{-1} \pmod {16} \\ && + 13^{-1} \pmod {16} + 15^{-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{\phi(16)-1} \pmod {16} + 3^{\phi(16)-1} \pmod {16} + 5^{\phi(16)-1} \pmod {16} \\ && + 7^{\phi(16)-1} \pmod {16} + 9^{\phi(16)-1} \pmod {16} + 11^{\phi(16)-1} \pmod {16} \\ && + 13^{\phi(16)-1} \pmod {16} + 15^{\phi(16)-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{8-1} \pmod {16} + 3^{8-1} \pmod {16} + 5^{8-1} \pmod {16} \\ && + 7^{8-1} \pmod {16} + 9^{8-1} \pmod {16} + 11^{8-1} \pmod {16} \\ && + 13^{8-1} \pmod {16} + 15^{8-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{7} \pmod {16} + 3^{7} \pmod {16} + 5^{7} \pmod {16} \\ && + 7^{7} \pmod {16} + 9^{7} \pmod {16} + 11^{7} \pmod {16} \\ && + 13^{7} \pmod {16} + 15^{7} \pmod {16} \Big) \pmod {16} \\\\ &=& ( 1^{7}+ 3^{7} + 5^{7} + 7^{7} + 9^{7}+ 11^{7} + 13^{7}+ 15^{7} ) \pmod {16} \\\\ &=& ( 1+ 2187 + 78125 + 823543 + 4782969 \\ && + 19487171 + 62748517+ 170859375 ) \pmod {16} \\\\ &=& 258781888 \pmod {16} \\\\ &=& 16173868\cdot 16 \pmod {16} \\\\ &\mathbf{=}&\mathbf{ 0 \pmod {16} } \\ \hline \end{array}\)

 

laugh

 Jul 30, 2018

18 Online Users

avatar