ProjectEuler 272 -- Remark (Unsolved)

Define N(n) as the number of the integers x, for which 0 <= x < n and x^3 = 1 (mod n).

Lemma 1: Let f(x) = a_n x^n + ... + a_n x^2 + a_1 x + a_0.  If f(x) = 0 (mod p) and f'(x) = 0 (mod p) has no common zeros, then #{ V(f(x) = 0 (mod p^e)) } = #{ V(f(x) = 0 (mod p)) }.

Lemma 2: If gcd(m, n) = 1, then #{ V(f(x) = 0 (mod mn)) } = #{ V(f(x) = 0 (mod m))} * #{ V(f(x) = 0 (mod n)) }.

Lemma 3: #{ V(x^k = 0 (mod p)) } = gcd(k-1, p).

So, we need to count the number of all numbers of the form p_1 p_2 ... p_5 q_1 ... where p_i are of the form 3h+1 and q_j otherwise.

C(n) = N(n) - 1.