Tag Info

New answers tagged


Think of what the definitions of "NP", "NP-complete" and "NP-hard" mean. NP means: Easy enough to be solved in polynomial time by a non-deterministic computer. NP-hard means: Hard enough so that every problem in NP can be solved by converting it to our problem in polynomial time, solving the problem, and converting the solution back in polynomial time. ...


For primes $p > 5$, the Binet formula applies mod $p$, in the following sense. If $p \equiv \pm 1 \mod 5$, $5$ is a quadratic residue mod $p$, and $z^2 - z - 1$ has two roots $\phi_\pm = (1 \pm \sqrt{5})/2$ in ${\mathbb Z}_p$. Then $F_n \equiv ((\phi_+^n - \phi_-^n)/\sqrt{5} \mod p$. In particular, $F_{p-1}$ is divisible by $p$, so $\gcd(p, F_{p-1}) = ...

Top 50 recent answers are included