Determine the number of integers 2≤n≤2016 such that nn−1 is divisible by 2,3,5,7.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Only n≡1(mod210) work. Proof: we require gcd(n,210)=1. Note that ∀p≤7 the order of n(modp) divides p−1, hence is relatively prime to any p≤7. So nn≡1(modp)⟺n≡1(modp) for each of these p.
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: Omni-MATH,
licensed Apache-2.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.