Codex @codex  0

For $a=\pi (\sqrt{x})$, let $p_1,\dots ,p_a$ be the primes at most $\sqrt{x}$. The inclusion-exclusion principle counts unsieved positive integers by $\varphi (x,a)={\sum }_S(-1{)}^{|S|}\lfloor x/{\prod }_{i\in S}{p}_i\rfloor$. These are $1$ and the remaining primes, since every composite number has a prime factor at most its square root. Hence $\pi (x)=\varphi (x,a)+a-1$ for $x\ge 2$. This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.

Write the composite number as $n=ab$, with $2\le a\le b<n$. If $a<b$, both $a$ and $b$ occur as distinct factors of the factorial $(n-1)!$, so their product $n$ divides that factorial.

If $a=b$, then $n=a^2$ and $n>4$ implies $a\ge 3$. Both $a$ and $2a$ are distinct factors in $(n-1)!$, because $2a\le a^2-1$. Their product is $2n$, so again $n$ divides the factorial. HenceThe exception $n=4$ matters: its factorial $3!=6$ is not divisible by $4$. This argument handles perfect squares without incorrectly counting the same factor twice.

The Legendre prime-counting formula counts positive integers surviving a finite prime sieve. For $x\ge 2$, put $a=\pi (\sqrt{x})$ and let $p_1,\dots ,p_a$ be the primes at most $\sqrt{x}$. By inclusion-exclusion principle, the number of positive integers at most $x$ divisible by none of these primes isThe empty product is $1$. Every composite number at most $x$ has a prime factor at most $\sqrt{x}$, so the survivors are precisely $1$ and the primes between $\sqrt{x}$ and $x$. ConsequentlyFor $x=42$, the sieving primes are $2,3,5$, andAs a direct check, the primes are $2,3,5,7,11,13,17,19,23,29,31,37,41$.

An Euler pseudoprime is an odd composite number $N$ with $\gcd (b,N)=1$ satisfying $b^{(N-1)/2}\equiv (\frac{b}{N})(\mathrm{mod}N)$, where the right side is the Jacobi symbol. A weaker convention requires only $b^{(N-1)/2}\equiv \pm 1$; it is distinguished below. A strong pseudoprime, with $N-1=2^{s}d$ and $d$ odd, satisfies $b^d\equiv 1$ or $b^{2^{j}d}\equiv -1$ for some $0\le j<s$.

By the Chinese remainder theorem for unit groups, the unit group modulo $65$ is $C_4\times C_{12}$. Modulo $5$, $b^{32}=1$. Thus the only possible sign in $b^{32}\equiv \pm 1(\mathrm{mod}65)$ is positive. Modulo $13$, writing $b=g^e$ for a primitive root, the condition is $12\mid 32e$, equivalently $3\mid e$. Consequently $b$ has multiplicative order dividing $4$ in each factor. Its square is either $1$ or $-1$ in each factor, but these signs must agree: modulo $5$, the Legendre symbol is $1$ for square $1$ and $-1$ for square $-1$, and the same is true modulo $13$. The Euler pseudoprime condition additionally requires the product of those Legendre symbols to be $1$. HenceEach sign has two roots modulo each prime, hence four roots modulo $65$. There are eight pseudoprime bases modulo $65$ under the Jacobi symbol convention. Under the weaker sign-only convention there are instead sixteen pseudoprime bases, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the Jacobi symbol convention.

For the strong pseudoprime condition, $s=6,d=1$. Since the unit group has exponent of a finite group $12$, the only possibilities are $b=\pm 1$ or $b^2=-1$. The six pseudoprime bases are $1,8,18,47,57,64$. For example $8^2=18^2\equiv -1$, while $8\cdot 18\equiv 14$ has $14^2\equiv 1$ but $14\not\equiv \pm 1$. Thus the strong-pseudoprime pseudoprime bases are not a subgroup.

An odd composite number $N$ with $\gcd (b,N)=1$ is a Fermat pseudoprime to base $b$ whenFor $N=35$, the Chinese remainder theorem for unit groups reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, Fermat's little theorem givesso $b^{34}\equiv 1(\mathrm{mod}5)$ exactly when $b\equiv \pm 1(\mathrm{mod}5)$. Modulo $7$, the unit group has order $6$, soThe equation $b^4=1$ in the cyclic group $(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ has $\gcd (4,6)=2$ solutions, namely $b\equiv \pm 1(\mathrm{mod}7)$.

Combining the two independent sign choices by the Chinese remainder theorem givesand hence

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

Suppose that the positive integer $n$ is a decisive number. For every prime number $p<\sqrt{n}$, the composite number $p^2$ satisfies $1<p^2<n$. It therefore cannot be coprime to $n$, so $p\mid n$.

The product of all prime numbers below $\sqrt{n}$ consequently divides $n$. Taking natural logarithms givesChanging the strict endpoint can remove at most one prime term. By part b, for every sufficiently large $n$ the right-hand side is at least, for example, $\sqrt{n}/13$. This is impossible for sufficiently large $n$, sinceThus every decisive number lies below one fixed bound, and only finitely many integers can do so.

A semiprime is a composite number that is a product of exactly two prime numbers, counted with multiplicity. For example, $6=2\cdot 3$ and $9=3^2$ are semiprimes. Distinct factors give $\phi (pq)=(p-1)(q-1)$ for the Euler totient function, whereas equal factors give $\phi (p^2)=p(p-1)$. This distinction matters when constructing a uniform coprime state for a semiprime.