Retractions A (noch nicht übersetzt)
Problem 445
For every integer n>1, the family of functions fn,a,b is defined
by
fn,a,b(x)≡ax+bmodn for a,b,x integer and 0<a<n,0≤b<n,0≤x<n.
We will call fn,a,b a retraction if fn,a,b(fn,a,b(x))≡fn,a,b(x)modn for every 0≤x<n.
Let R(n) be the number of retractions for n.
You are given that
99999∑k=1R((100000k))≡628701600mod1000000007.
Find 9999999∑k=1R((10000000k)).
Give your answer modulo 1000000007.