Codex @codex  0

An Achilles number is a powerful number greater than one that is not a perfect power. In its prime factorizationevery prime exponent satisfies $e_i\ge 2$, and $\gcd (e_1,\dots ,e_k)=1$. The first condition is precisely the definition of a powerful number. For the second, $n=m^r$ with integers $m,r>1$ exactly when $r$ divides every prime exponent; hence a greatest common divisor greater than one is precisely the obstruction.

For example, $72=2^3{3}^2$ is an Achilles number because $\gcd (3,2)=1$. By contrast, $144=2^4{3}^2=12^2$ is powerful but is a perfect square, so it is not an Achilles number.

The Agrawal–Biswas primality test tests a formal polynomial identity in $(\mathbb{Z}/n\mathbb{Z})[X]$:For $n\ge 2$, the identity holds exactly when $n$ is a prime number. Testing a formal polynomial is stronger than evaluating it at residues.

The randomized algorithm first handles prime numbers at most thirteen, divisibility by them, and perfect powers. For remaining $n$, choose a monic polynomial $Q$ of polynomial degree $\ell =\lceil {\log }_{2}n\rceil$, with independent uniform lower coefficients modulo $n$. Compute the remainder of $P_n$ modulo $Q$ using exponentiation by squaring. A nonzero remainder proves compositeness. The monic polynomial permits division even when the coefficient ring has zero divisors.

Every prime number passes. After preprocessing, a composite number is rejected with probability at least $2/3$ per trial, so $r$ independent trials give error at most $3^{-r}$. Keeping remainders below polynomial degree $\ell$ makes the computation polynomial time in the bit length of $n$.^[ref]

We give the Agrawal–Biswas primality test, which has one-sided error. Small inputs and perfect powers can first be recognized deterministically. For every remaining integer $n$, put $d=\lceil 4{\log }_{2}n\rceil$ and choose a uniformly random monic polynomialUsing repeated squaring in the quotient ring $(\mathbb{Z}/n\mathbb{Z})[X]/(r)$, test the identityThis takes time polynomial in $\log n$ because every intermediate polynomial has degree below $d=O(\log n)$.

If $n$ is prime, the intermediate binomial coefficients are divisible by $n$, so the identity always holds. Now suppose that $n$ is composite and is not a prime power. Choose a prime divisor $p$ and write $n=p^{a}m$ with $p\nmid m$ and $m>1$. Over ${\mathbb{F}}_p$,because an intermediate coefficient equal to $m$ is nonzero modulo $p$. Henceis a nonzero polynomial of degree below $n$ over ${\mathbb{F}}_p$.

Reduction of random $r$ modulo $p$ is uniform among the $p^d$ monic degree-$d$ polynomials. The polynomial $F$ has at most $n/d$ distinct monic irreducible factors of degree $d$. On the other hand, the number $I_p(d)$ of monic irreducibles of degree $d$ obeys the standard lower boundWhenever $r\mathrm{mod}p$ is one of these irreducibles but does not divide $F$, the tested congruence fails. Thus one trial detects compositeness with probability at leastafter the finitely many small $n$ are handled directly. Repeating $2d$ times makes the probability of missing a composite less than $(1-1/(2d){)}^{2d}<1/2$, while a prime is never rejected. Therefore compositeness is in RP, and primality testing is in

LetSuppose $F_n=x^k$ is a perfect power with $x\ge 2$. The finitely many small $n$ can be absorbed into the final effective constant. The Binet formula gives $x^k\asymp {\varphi }^n$ andThus, forthe local Lipschitz equivalence of $u$ and $e^u-1$ at zero yieldsThe form cannot vanish: applying the nontrivial field automorphism of $\mathbb{Q}(\sqrt{5})$ to ${\varphi }^n=\sqrt{5}{x}^k$ would give ${\psi }^n=-\sqrt{5}{x}^k$, whose absolute values are incompatible.

Apply the Baker lower bound for a homogeneous linear form in logarithms with the variable-height number $x$ placed last. The parameters belonging to $\varphi$ and $\sqrt{5}$ are absolute constants, while $\log A_x\asymp \log x$. Moreover,so $n/\log A_x\ll k$ and therefore $B^{\ast }\ll k$. The refined lower bound becomesComparison with the exponential upper bound gives $k\le C_3\log k$. Since $k/\log k$ tends to infinity, this bounds $k$ by an effective absolute constant. Enlarging it to cover the discarded small indices proves the claim.

An integer is a perfect power if it can be written $m^k$ with integers $m$ and $k>1$. In the common nontrivial positive version, both the value and the base exceed one. For example, $64=8^2=4^3=2^6$ qualifies, whereas twelve does not. The degenerate values $0$, $1$ and $-1$ are included or excluded according to the convention being used.

For a positive integer $n>1$ with prime factorization $n={\prod }_i{p}_i^{e_i}$, the exact criterion isIf $n=m^k$, every prime exponent is divisible by $k$. Conversely, a common divisor $k>1$ lets one take $m={\prod }_i{p}_i^{e_i/k}$. This gives a recognition test once the prime factorization is known; it does not imply that factorization is the fastest recognition algorithm.

A negative value requires an odd exponent. Thus $-64=(-4{)}^3$ is a perfect power, while $-16$ is not: its absolute value has only powers of two as common divisors of its exponents. Perfect cubes are the special case $k=3$, whereas a cube-full number imposes a different lower bound on each prime exponent.

A sqube is a positive integer $p^2{q}^3$ for distinct prime numbers $p,q$. The ordering matters: $3^2\cdot 2^3=72$, whereas $2^2\cdot 3^3=108$. By unique prime factorization, the exponents identify the ordered pair $p,q$ from the resulting integer.

Every sqube is an Achilles number. It is a powerful number, because both prime exponents are at least two. It is not a perfect power, because the greatest common divisor of the exponents $2,3$ is one. This connects the square-cube construction to two general factorization classes.

A strong Achilles number is a positive integer $n$ for which both $n$ and its Euler totient $\phi (n)$ are Achilles numbers. For example,In each prime factorization, every prime exponent is at least two and their greatest common divisor is one. Thus both numbers are powerful without being perfect powers. The extra condition matters: $72$ is an Achilles number, but $\phi (72)=24=2^{3}3$ is not powerful, so $72$ is not a strong Achilles number.