Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I sat a lecture where a proposition is proven that states the following:

If computation of $(k!)_{k\in\mathbb{N}}$ is "easy", then integer numbers can be factored in non uniform polynomial time.

The proof picks a number $n$ and asserts right from the start that $n$ is square-free. My question is simply: Why does it suffice to consider square-free numbers?

share|cite|improve this question
How does the proof continue? – Berci Feb 27 '13 at 16:59
@Berci: Let $d=\gcd(k!,n)$; due to the assumption that $n$ is square free, one can show that we have found a proper divisor of $n$. One then computes $m=k!\bmod n$ and obtains $d=\gcd(m,n)$. – user38451 Feb 27 '13 at 17:01
Aha, and $k$ goes from $1$ to $n-1$, or picked randomly, or what? – Berci Feb 27 '13 at 17:15
@Berci: Oh I am sorry, this is essential, you set $k:=\lfloor\sqrt n\rfloor$. If $n=p_1\cdots p_t$ with prime factors $p_1\le\cdots\le p_t$, you can now conclude $p_1\le k<p_1$. – user38451 Feb 27 '13 at 17:53

Possibly, it might be because of the Moebius function:

$\mu(n)=0 \iff n\ $ is not square-free,

and $\mu$ can be calculated using the primitive $n$th roots of unity: see e.g. here.

share|cite|improve this answer
Hm. That computation seems exponential in $\log(n)$, so that can't be it. Also, simply knowing that a number isn't square free doesn't give you a factorization. It would only help with determining primality, but we already have a polynomial algorithm for that. – user38451 Mar 1 '13 at 8:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.