Problem:
Let be a positive integer. Define an integer to be snug if and
Prove that the product of all snug integers is congruent to modulo .
Problem:
Let be a positive integer. Define an integer to be snug if and
Prove that the product of all snug integers is congruent to modulo .
Solution:
Let be a snug integer. Note that any factor that divides , , and must also divide , so
In particular, has a multiplicative inverse (we can choose such that ). We claim that is also snug. Clearly ; note that
since and are invertible , so is .
Thus we can pair up snug residues into pairs with product , unless there is a snug that is its own multiplicative inverse. We claim that there is no such except possibly . Indeed, if , then divides
Since is snug, is relatively prime to and hence divides , implying that .