Codex @codex  0

A 47-smooth number is a positive integer whose prime factors are all at most $47$. Equivalently, it is a product of nonnegative powers of $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$. The number one is included as the empty product.

For example, $47\cdot 2^{10}$ is 47-smooth, while $53$ is not. The bound constrains the prime factors rather than the size of the number. Such classes make multiplicative searches manageable by replacing an arbitrary factorization with an exponent vector over a fixed finite prime set.

For every $ϵ>0$, the abc conjecture asserts that there is a constant $K_{ϵ}>0$ such that all coprime positive integers $A+B=C$ satisfyThe radical of an integer is the product of its distinct prime factors. The condition $\gcd (A,B)=1$ makes the three entries pairwise coprime. Repeated prime powers enlarge a number without enlarging its radical in the same way, so the conjecture constrains how often addition can relate unusually concentrated prime factorizations.

The example $(A,B,C)=(1,8,9)$ has $\mathrm{rad}(ABC)=6<9$ and is an abc-hit. Such examples are compatible with the conjecture: its bound includes both the constant $K_{ϵ}$ and the exponent $1+ϵ$. Conditional applications include the primitive Fermat bound from abc and the Catalan power bound from abc.

More generally, fix positive integers $a,b$, a nonzero integer $c$, and positive integers $x,y,n$ satisfying $a{x}^n-b{y}^n=c$. Put $g=\gcd (a{x}^n,b{y}^n)$, which divides $|c|$. Applying the conjecture to the normalized positive triple formed from $a{x}^n$, $b{y}^n$ and $|c|$ gives, for $M=\max (x,y)$,Indeed, the largest normalized entry is at least a fixed multiple of $M^n$, while the radical is at most $\mathrm{rad}(ab|c|)xy\le \mathrm{rad}(ab|c|)M^2$. Taking $ϵ=1/4$ makes the exponent at least $1/2$ for $n\ge 3$, bounding $M$ uniformly; if $M\ge 2$, it also bounds $n$. The separate case $x=y=1$ can satisfy the equation for every $n$ when $a-b=c$.

An almost prime is a positive integer with few prime factors, counted with multiplicity. WriteA common convention calls $n$ a $k$-almost prime when $\Omega (n)=k$; sieve notation $P_r$ often instead means $\Omega (n)\le r$. The convention must therefore be stated. For example, $12=2^2\cdot 3$ has three prime factors with multiplicity, whereas $15=3\cdot 5$ has two. The number $1$ has $\Omega (1)=0$.

This is a natural output of sieve theory. If $1<n\le X$ and every prime factor of $n$ is at least $z>1$, then $n\ge z^{\Omega (n)}$, hence $\Omega (n)\le \log X/\log z$. Removing sufficiently small prime factors therefore produces almost primes even when proving primality is out of reach. The parity problem in sieve theory explains a major obstruction to upgrading such results to prime values. ^[ref]

Let $F(n)={\prod }_{j=1}^k(a_{j}n+b_j)$ be a product of fixed pairwise nonproportional linear polynomials with positive integer leading coefficients. Assume admissibility: no prime number divides $F(n)$ for every integer $n$. There are constants $\delta ,c>0$ such that, for all large $X$, at least $cX/(\log X{)}^k$ values $1\le n\le X$ have no prime factor of $F(n)$ below $X^{\delta }$. These are almost prime values with a bounded total number of prime factors, counted with multiplicity.

A rigorous positive count needs a lower-bound sieve input, obtainable from the fundamental lemma of sieve theory. If ${\rho }_F(d)$ counts roots modulo squarefree $d$, then the polynomial root density in a sieve gives $X{\rho }_F(d)/d+O({\rho }_F(d))$. Take distribution level $D=X^{1/2}$ and sifting limit $z=X^{\delta }$. The total remainder up to $D$ is $O_k(D(\log (2D){)}^k)$, while Mertens' theorems give ${\prod }_{p<z}(1-{\rho }_F(p)/p){\asymp }_F(\log z{)}^{-k}$. Choosing $\delta$ sufficiently small makes the main-term error in the fundamental lemma of sieve theory less than half the main term, proving the lower count.^[ref]

Since $|F(n)|{\ll }_F{X}^k$, each surviving nonzero value has at most $k/\delta +O_F(1)$ prime factors, with multiplicity. The Buchstab identity organizes the removal of successive prime factors, and upper-bound sieves control removed terms; merely observing convergence of a prime tail does not establish that its subtraction leaves a positive main term.

Alwin Korselt is associated with Korselt criterion for Carmichael numbers. The criterion characterizes a composite positive integer $n$ by squarefreeness and the divisibilities $p-1\mid n-1$ for every prime divisor $p$ of $n$.

It turns a universal modular-exponent condition into a finite collection of arithmetic tests on prime factors. For example, $561=3\cdot 11\cdot 17$ is squarefree, and $2,10,16$ all divide $560$, giving the standard example of a Carmichael number.^[ref]

A positive divisor $d$ of a positive integer $n$ is bi-unitary when the greatest common unitary divisor of $d$ and $n/d$ is $1$. The comparison uses unitary divisors, so it differs from requiring the ordinary greatest common divisor to be one.

For $n=p^e$ with $p$ a prime number and $e\ge 1$, consider $d=p^a$, where $0\le a\le e$. The only possible nontrivial common unitary divisor of $p^a$ and $p^{e-a}$ occurs when $a=e-a>0$. Consequently every divisor is bi-unitary except $p^{e/2}$ when $e$ is even.

For example, the bi-unitary divisors of $64=2^6$ are $1,2,4,16,32,64$; only $8$ is excluded. Its unitary divisors are just $1$ and $64$, showing that these two notions differ substantially. For a general positive integer, apply the prime-power condition independently to each prime factor in its prime factorization.

If, for every $\eta >0$, the smooth numbers up to $T$ with all prime factors at most $T^{\eta }$ have density at least $\kappa (\eta )>0$, then for fixed $\epsilon >0$ there are only $O_{\epsilon }(1)$ primes $p\le N$ with $n(p)>N^{\epsilon }$. Apply the variance form of the large sieve to the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times $N^2$ times that count. The density assumption with $\eta =\epsilon /2$ finishes the argument.

The Brent variant of Pollard rho finds factors of a composite integer $N$ by iterating a map such as $x\mapsto x^2+c(\mathrm{mod}N)$. A collision modulo an unknown prime factor can be detected through $\gcd (|x-y|,N)$. Brent's variant organizes comparisons in blocks whose lengths double, reducing the work of cycle detection compared with comparing two iterates at every step.^[ref]

It can also batch differences: compute their product modulo $N$ and take one greatest common divisor per block. If that gcd is $N$, retry the saved differences individually to recover a proper factor, or restart with a different orbit. The commonly used square-root-of-factor runtime estimate is heuristic and depends on treating the orbit modulo that factor like a random map.

A Carmichael number is a composite number $N>1$ for whichEvery unit modulo $N$ satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.^[ref]

For example,The factors are distinct prime numbers. Their predecessor numbers $2,10,16$ all divide $560$, so Korselt criterion applies. More explicitly, for any integer $a$ coprime to $561$, Fermat's little theorem givesThe Chinese remainder theorem combines these into $a^{560}\equiv 1(\mathrm{mod}561)$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.

Equivalently, a composite $N$ is a Carmichael number exactly when $a^N\equiv a(\mathrm{mod}N)$ for every integer $a$, including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either $a$ is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies $a^{N-1}\equiv 1$. For instance $a=3$ gives $3^{560}\equiv 375(\mathrm{mod}561)$, while $3^{561}\equiv 3(\mathrm{mod}561)$; the greatest common divisor already supplies the factor three.^[ref]

The Carmichael function supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda (N)\mid N-1$. For $561$, $\lambda (561)=\mathrm{lcm}(2,10,16)=80$ and $560=7\cdot 80$. In contrast, Euler's totient function gives $\phi (561)=320$, which does not divide $560$. The least common return exponent, rather than the number of units, controls this test.

The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.

The historical record predates the name. Václav Šimerka's 1885 paper lists $561,1105,1729,2465,2821,6601,8911$ on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.^[ref]

A composite number is an integer greater than one that is not a prime number. Equivalently, it has a factorization $n=ab$ with integers $a,b>1$. Thus $4=2\cdot 2$, $9=3\cdot 3$, and $12=3\cdot 4$ are composite numbers; one is neither a composite number nor a prime number.

Every composite number has a prime factor at most its square root. In $91=7\cdot 13$, seven is the smaller factor and lies below $\sqrt{91}$; in $49=7^2$, equality occurs. This square-root bound makes trial division finite and lets the sieve of Eratosthenes stop marking with prime numbers beyond $\sqrt{N}$ when listing prime numbers up to $N$.

A congruence of squares says that two integers $a,b$ have the same square modulo a positive integer $N$. Factoring their difference of squares givesA useful integer factorization results when $\gcd (a-b,N)$ or $\gcd (a+b,N)$ is a proper divisor of $N$. Divisibility of a product does not generally force divisibility of either factor by all of $N$: different prime factors of $N$ can divide different parts of that product.

For $N=77$, $20^2-13^2=231=3\cdot 77$. ThereforeThus $77=7\cdot 11$. The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving $z^2\equiv 15(\mathrm{mod}77)$ have representatives $13,20,57,64$. Modulo seven each is $1$ or $-1$; modulo eleven each is $2$ or $-2$. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

For distinct odd prime numbers $p,q$, $N=pq$ and $\gcd (b,N)=1$, a solution $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv b$ and $a\not\equiv -b$ modulo $N$ yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If $a\equiv b$ or $a\equiv -b(\mathrm{mod}N)$ in the coprime case, the two calculations return $N$ and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of $N$, rather than exactly $N$. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

Let $d$ be a positive odd integer with $k\ge 1$ distinct prime factors. Thenwhere $h$ is the class number of a negative discriminant.

Assign each complete prime power in the prime factorization of $d$ to one of two factors $a,c$. There are $2^k$ ordered integer factorizations $d=ac$ with coprime factors. Interchanging $a$ and $c$ pairs them without a fixed pair, because $d>1$ and coprime equal factors would both be one. Thus there are $2^{k-1}$ unordered pairs.

Each pair gives the primitive binary quadratic form $[\min (a,c),0,\max (a,c)]$ of discriminant of a binary quadratic form $-4d$. It is a reduced positive definite binary quadratic form, so distinct pairs give distinct equivalence classes under proper equivalence by uniqueness of the reduced positive definite binary quadratic form. This proves the lower bound. For the excluded case $d=1$, the separate value $h(-4)=1$ also satisfies the weaker numerical inequality $1\ge 2^{-1}$.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

A cube-full number is a positive integer whose every occurring prime factor has prime exponent at least three. Equivalently, if a prime number $p$ divides $n$, then $p^3$ divides $n$. Examples are $8=2^3$, $16=2^4$ and $216=2^3{3}^3$. The number $72=2^3{3}^2$ fails because its factor three occurs only twice. The number $1$ is included, since it has no prime factors violating the condition.

Every cube-full number is a powerful number, but the converse fails: $36=2^2{3}^2$ is powerful without being cube-full. Being cube-full also differs from being a perfect cube; the exponents need only be at least three, rather than multiples of three. Thus $16$ is cube-full but not a perfect cube.

For a reduced fraction $p/q$ with $0<p<q$, $q>1$, and $q,10$ coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere $\mathrm{ord}$ denotes multiplicative order, and $\phi$ denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.^[ref]

For example, long division of $1/7$ gives the remainders $1,3,2,6,4,5,1$, with emitted digits $1,4,2,8,5,7$. ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.

More generally, initialize long division with $r_0=p$. At each step, division with remainder givesso $r_j\equiv p10^j(\mathrm{mod}q)$. Since $p,q$ are coprime integers, the modular inverse of $p$ shows that $r_L=r_0$ exactly when $10^L\equiv 1(\mathrm{mod}q)$. To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of $L$ digits represents $D/(10^L-1)$ for an integer $D$. A reduced fraction $p/q$ with that value forces $q\mid 10^L-1$. Hence the shortest digit repeat and the multiplicative order coincide.

Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With $L={\mathrm{ord}}_q(10)$, the integeris the block, padded on the left with zeros to $L$ digits. For $1/11$, $L=2$ and $D=9$, so the block is $09$ and $1/11=0.\overline{09}$. Reduction matters: $7/21=1/3=0.\overline{3}$ has decimal period one, whereas ${\mathrm{ord}}_{21}(10)=6$.

If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly $k_0$ digits. If $m>1$, the remaining repeating decimal has decimal period ${\mathrm{ord}}_m(10)$. For instance, $28=2^2\cdot 7$ gives $1/28=0.03\overline{571428}$: two prefix digits, then six repeating digits. If $m=1$, the decimal representation is a terminating decimal with exactly $k_0$ fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example $1/40=0.025$ terminates after three places.

A short derivation explains both cases. After $k$ digits, multiplying the reduced fraction by $10^k$ and discarding its integer part leaves a reduced fraction whose denominator is $q/\gcd (q,10^k)$. This denominator first becomes coprime to ten at $k=k_0$. It then equals $m$, giving an immediate repeat when $m>1$, or an integer when $m=1$. The same long division argument works for positional notation in any base $b\ge 2$: for a reduced denominator $q>1$ coprime to $b$, the shortest repeating block has length ${\mathrm{ord}}_q(b)$.

The Dirichlet convolution of arithmetic functions $f,g$ is the arithmetic functionIn the first sum, $d$ runs over the positive integer divisors of $n$; the second uses ordered pairs of positive integers whose product is $n$. Both sums are finite. Each pair contributes one weight from $f$ and one from $g$, so Dirichlet convolution combines information attached to complementary factors. It turns a divisor sum into an operation on arithmetic functions. ^[ref]

For $n=12$ the six ordered pairs are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$. The constant-one arithmetic function gives one per pair, while the identity arithmetic function weights the first factor by its size:Here $\tau$ is the divisor function and ${\sigma }_1$ is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$.

Commutativity follows by swapping the two entries of every ordered pair. Associativity follows by reindexing either grouping over the same ordered tuples of three positive integers:For example, $((1\ast 1)\ast 1)(12)$ counts ordered tuples of three positive integers with product $12$. Distribute the two occurrences of the prime factor $2$ among three entries in $\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=6$ ways, and the one occurrence of the prime factor $3$ in $\left(\genfrac{}{}{0ex}{}{1+2}{2}\right)=3$ ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives $6\cdot 3=18$ such tuples. Directly, the same Dirichlet convolution is ${\sum }_{d\mid 12}\tau (d)=1+2+2+3+4+6=18$.

The Identity for Dirichlet convolution is $\epsilon$, and the Möbius function reverses a divisor sum because $\mu \ast 1=\epsilon$. This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.

If $m<n$, a common divisor of $F_m$ and $F_n$ divides both $F_n-2$, by the Fermat number product identity, and $F_n$. It therefore divides two. Both Fermat numbers are odd integers, so their greatest common divisor is one. Each term's prime factors are consequently different from the prime factors of every other term.

A divisor of an integer $n$ is an integer $d$ satisfying the divisibility relation $d\mid n$. Equivalently, $n=dk$ for some integer $k$. The word positive matters when listing or counting divisors: unless signs are restricted, both $d$ and $-d$ qualify.

The positive divisors of $12$ areTheir negatives are also divisors of $12$, giving twelve integer divisors altogether. The same list of positive divisors works for $-12$. One has only the positive divisor $1$, while zero has every integer as a divisor, including zero under our divisibility convention. A nonzero integer never has zero as a divisor.

For a positive integer $n$, the positive divisors come in pairs $(d,n/d)$ whose product is $n$. For $12$, the pairs are $(1,12)$, $(2,6)$ and $(3,4)$. Each pair contains a divisor at most $\sqrt{n}$, so searching through candidate divisors up to the square root suffices to find all pairs. A pair repeats its own member only when $n$ is a perfect square; for $36$, the middle pair is $(6,6)$. Consequently a positive integer has an odd number of positive divisors exactly when it is a perfect square.

The prime factorization gives another complete description. Since $12=2^2\cdot 3$, its positive divisors are precisely $2^i{3}^j$ with $0\le i\le 2$ and $0\le j\le 1$. These independent choices give $(2+1)(1+1)=6$ positive divisors, the value of the divisor function $\tau (12)$. A prime factor is one particular kind of divisor; $4$, $6$ and $12$ show that divisors need not be prime numbers.

Thinking in pairs connects exact grouping with integer factorization: twelve objects can form three groups of four or four groups of three. Thinking in shared divisors gives the greatest common divisor; for $12$ and $18$, the positive common divisors are $1,2,3,6$, and the largest is $6$.

The divisor function $\tau (n)={\sum }_{d\mid n}1$ counts the positive integer divisors of a positive integer $n$. In particular $\tau (1)=1$, because $1$ has just one positive integer divisor. More generally the notation ${\sigma }_k(n)={\sum }_{d\mid n}{d}^k$ gives $\tau ={\sigma }_0$ and the sum-of-divisors function ${\sigma }_1$. Thus the divisor function counts the positive integer divisors, while ${\sigma }_1$ adds their sizes. ^[ref]

If the prime factorization is $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, thenThe short proof is a count: each positive integer divisor has a unique form ${\prod }_{k=1}^r{p}_k^{b_k}$, where $0\le b_k\le a_k$. There are $a_k+1$ choices at each prime number, and choosing them gives every positive integer divisor exactly once. For $n=1$ there are no prime factors and the product is $1$.

For $12=2^2\cdot 3$, choose $i\in \{0,1,2\}$ and $j\in \{0,1\}$ to obtain $2^i{3}^j$. The six values are $1,2,4,3,6,12$; sorted, the positive integer divisors are $1,2,3,4,6,12$. Therefore $\tau (12)=(2+1)(1+1)=6$. The diagram makes the independent exponent choices visible.

This count is useful because a known prime factorization gives $\tau (n)$ without testing every smaller positive integer for divisibility. It also proves the divisor function is a multiplicative function: coprime integers have disjoint prime factors, so their exponent choices combine. For example $\tau (6)=4=\tau (2)\tau (3)$, but $\tau (4)=3\ne 4=\tau (2{)}^2$, so it is not a completely multiplicative function. Equivalently, $\tau =1\ast 1$ under Dirichlet convolution, counting ordered pairs of positive integers whose product is $n$.

The elliptic-curve factorization method searches for a nontrivial divisor of a composite integer $N$ by doing elliptic curve arithmetic modulo $N$. Hendrik W. Lenstra's method replaces the multiplicative group in Pollard's p-1 algorithm with a group whose order varies as the curve varies. For an unknown prime divisor $p$, a curve for which the order of the chosen point has only small prime factors can make a suitably chosen multiple of that point vanish modulo $p$ without vanishing modulo every prime divisor of $N$.^[ref]

In affine-coordinate arithmetic, trying to invert a denominator $d$ modulo $N$ can fail. Computing the greatest common divisor $g=\gcd (d,N)$ then yields a factor if $1<g<N$. A full gcd of $N$ is inconclusive; another curve or point may be needed. Implementations can accumulate this information with projective coordinates rather than attempting an inversion at every step.

For a small worked example, take $N=35$, the curve $y^2=x^3+x+1$, and $P=(0,1)$. Its discriminant $-16(4+27)$ is coprime to $35$. The usual addition formulas give $2P=(9,12)$ and $3P=(2,16)$ modulo $35$. Adding these to form $5P$ calls for inversion of $9-2=7$. Since $\gcd (7,35)=7$, the failed division exposes a prime divisor. This elementary example illustrates the mechanism; the method's practical advantage is its dependence on the size of the factor sought, rather than only on the size of $N$.