Maths Olympiad Prep

Library / /9 of 24

Number theory Difficulty 4.8 AIME Prove it United States

Problem:

Let n>3n > 3 be a positive integer. Define an integer kk to be snug if 1k<n1 \leq k < n and
gcd(k,n)=gcd(k+1,n). \gcd(k, n) = \gcd(k+1, n).
Prove that the product of all snug integers is congruent to 11 modulo nn.

Solution

Solution:

Let kk be a snug integer. Note that any factor that divides nn, kk, and k+1k+1 must also divide (k+1)k=1(k+1)-k=1, so
gcd(k,n)=gcd(k+1,n)=1. \gcd(k, n) = \gcd(k+1, n) = 1.
In particular, kk has a multiplicative inverse hmodnh \bmod n (we can choose hh such that 0<h<n0 < h < n). We claim that hh is also snug. Clearly gcd(h,n)=1\gcd(h, n) = 1; note that
(h+1)k=hk+kk+1(modn); (h+1) \cdot k = h k + k \equiv k + 1 \pmod{n};
since kk and k+1k+1 are invertible modn\bmod n, so is h+1h+1.
Thus we can pair up snug residues modn\bmod n into pairs with product 11, unless there is a snug kk that is its own multiplicative inverse. We claim that there is no such kk except possibly k=1k=1. Indeed, if k21(modn)k^2 \equiv 1 \pmod{n}, then nn divides
k21=(k+1)(k1). k^2 - 1 = (k+1)(k-1).
Since kk is snug, nn is relatively prime to k+1k+1 and hence divides k1k-1, implying that k=1k=1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.