# Testing whether the Euler Totient of a number equals to certain value

I have solved a problem in Project Euler. My solution was based on the finding the all numbers whose Euler Totient value equals to $$13!$$

However, while I was working on the problem, I thought that: "Can I find an algorithm that tests whether the Euler Totient of a number equals to $$13!$$ ?" I know that finding $$\phi(n)$$ is as hard as factoring $$n$$. On the other hand, we can easily test whether a specific number is a factor or not.

We have probabalistic primality tests such as: Fermat's, Euler's, Miller-Rabin etc. We can test the primality of a number efficiently. Can we use same approach to test "Is $$\phi(n)$$ equals to specific number?"

We know that $$a^{\phi(n)} \equiv 1\pmod n$$ if $$\gcd(a,n) = 1$$ by Euler's Theorem. Can we use this congruence to test probabilistically whether the Euler Totient of a number equals to certain value like in primality tests mentality?

Or more generally, What is the most efficient way of testing whether the Euler Totient of a number equals to certain value?

• Oops, I misread that as 13 exclamation point instead of 13 factorial, which makes the problem quite trivial. Nevertheless, you want a fast test whether $\varphi(n)=m$. May we assume that $n$ may be arbitrarily wild, but $m$ is nice and (as is the case with $m=13!$) we know the prime factorization of $m$? In that case, there is a simple upper bound for $n$ and we can easily find all prime factors of $n$ (namely, primes dividing $m$, and primes dividing some $d+1$ where $d\mid m$). Feb 3 at 21:29
• @HagenvonEitzen this still can turn to be an answer.. Feb 3 at 22:34
• @Hagen von Eitzen Actually my question is more general. In 13! case, there is no problem to factor n whose Euler Totient equals 13! as you say. However, I'dont remember the exact count but there are potential prime factors for n more than 400. Even if I know the all potential factors, factoring n and computing phi(n) is not efficient as I would like. Feb 4 at 22:48

There is a tighter form of Euler's theorem for composite numbers that says that $$a^{\lambda(n)}\equiv 1\pmod n$$ for $$(a,n)=1$$ where $$\lambda(n)$$ is the Carmichael function. The Carmichael function always divides $$\phi(n)$$ but (for example) for odd composite numbers it is always less than $$\phi(n)$$. Therefore simply testing to see if $$13!$$ is a multiple of the order of random residues (and there there exist random residues where the order is exactly 13!) won't allow us to distinguish numbers where $$\lambda(n)=13!$$ but $$\phi(n)>13!$$.
However, a you note we can compute $$\phi(n)$$ if we can factor $$n$$ and it turns out that the numbers where $$\phi(n)=13!$$ are very easy to factor using a variant of Pollard's $$p-1$$ algorithm. Given a candidate non-prime $$n$$, we pick a random $$a$$ (we can check if $$(a,n)=1$$ and divide out a GCD is it is), raise it to the power $$13!/1024$$ modulo $$n$$ and there is a very good chance that the answer is not $$\pm 1$$ (we can even raise the odds by choosing $$a$$ with Jacobi symbol -1 mod $$n$$). Writing the answer as $$x$$ we compute $$x^2, x^4, \ldots , x^{1024}\mod n$$ by squaring. Eventually the sequence becomes all 1s (the last value is certainly 1) and the previous value is either -1 or a non-trivial square root of unity, say $$y$$ such that $$y^2\equiv 1\pmod n$$. In this case $$\mathrm{GCD}(n,y\pm1)$$ splits $$n$$ into two smaller numbers. The method recurses and I'll leave the details to you.