Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

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

Express your answer as an integer from to , inclusive.
Solution
Since is even and only has a prime factor of , all of the odd numbers are relatively prime with and their modular inverses exist. Furthermore, the inverses must be distinct: suppose that . Then, we can multiply both sides of the congruence by to obtain that .

Also, the modular inverse of an odd integer must also be odd: if the modular inverse of was of the form , then , but the left-hand side is even and the right-hand side is odd.

Thus, the set of the inverses of the first positive odd integers is simply a permutation of the first positive odd integers. Then,
Final answer
0