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.
+26367 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}\)
