+0  
 
0
37
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.

Guest Jul 29, 2018
 #1
avatar+19835 
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

heureka  Jul 30, 2018

14 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.