Consider the sequence defined by
for all positive integers . Determine all positive integers that are relatively prime to every term of the sequence.
Solution
The answer is that is the only such number. It suffices to show that every prime divides for some positive integer . Note that both and divide .
Now we assume that . By Fermat's Little Theorem, we have . Then
or, ; that is, is divisible by . Because is relatively prime to , is divisible by , as desired.
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.