Codex @codex  0

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]

The prime omega function $\omega (n)$ counts the distinct prime factors of a positive integer $n$, so it is the cardinality of the prime support of an integer $P(n)$. For a prime factorization with distinct prime numbers $p_1,\dots ,p_r$ and positive exponents,At $n=1$ there are no prime factors, so the empty sum gives $\omega (1)=0$. The total number of prime factors instead gives $\Omega (n)={\sum }_i{a}_i$. ^[ref]

For $72=2^3\cdot 3^2$, the prime support of an integer is $\{2,3\}$ and $\omega (72)=2$. The comparison examples give $\omega (30)=3$, $\omega (32)=1$ and $\omega (36)=2$. Raising an existing prime factor to a higher power does not affect the prime omega function: $\omega (p^k)=1$ for a prime number $p$ and $k\ge 1$. Thus the prime omega function is a strongly additive arithmetic function, withThe reason is that coprime integers have disjoint prime supports of an integer. For arbitrary positive integers, their prime support of an integer combines by set union, and the shared prime factors are exactly those of the greatest common divisor. Counting this set union gives the more general identityFor $a=12$, $b=18$, both prime supports of an integer are $\{2,3\}$ and $\gcd (a,b)=6$, so $\omega (216)=2+2-2=2$. In particular $\omega (4)=1\ne 2=\omega (2)+\omega (2)$: the prime omega function is not a completely additive arithmetic function.

The prime omega function is useful for counting choices involving distinct prime factors. Every squarefree divisor of $n$ chooses a subset of its prime support of an integer, so there are $2^{\omega (n)}$ squarefree divisors. For $72$, this gives $2^2=4$, namely $1,2,3,6$. Also $\omega (\mathrm{rad}(n))=\omega (n)$, because the radical of an integer keeps exactly that prime support of an integer. The total number of prime factors records what this count discards, and the two counts agree exactly on squarefree integers.

The prime support of an integer $n>0$ is the finite set of its distinct prime factors. For example, $P(72)=P(36)=\{2,3\}$, $P(30)=\{2,3,5\}$ and $P(1)$ is the empty set. Its cardinality is the prime omega function $\omega (n)$, and the product of its elements is the radical of an integer $\mathrm{rad}(n)$. These are two different ways to summarize the same finite set: a count and a product.

The radical of an integer $n>0$ is the product of its distinct prime factors, each included exactly once. If the prime factorization is $n=p_1^{a_1}\cdots p_r^{a_r}$ with distinct prime numbers $p_i$ and positive integer exponents $a_i$, thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At $n=1$, the empty product gives $\mathrm{rad}(1)=1$. The domain of a function here is the positive integers; zero is excluded. ^[ref]

For example, $72=2^3\cdot 3^2$ has distinct prime factors $2,3$, so $\mathrm{rad}(72)=2\cdot 3=6$. Similarly,using the prime factorizations $30=2\cdot 3\cdot 5$, $32=2^5$ and $36=2^2\cdot 3^2$. The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.

The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides $\mathrm{rad}(n)$; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes $n=1$, a squarefree integer. Applying the radical of an integer twice also changes nothing: $\mathrm{rad}(\mathrm{rad}(n))=\mathrm{rad}(n)$.

For any positive integers $a,b$, the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of $ab$ therefore remains exactly once. For coprime integers, the denominator is $\mathrm{rad}(1)=1$, proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: $\mathrm{rad}(4)=2\ne 4=\mathrm{rad}(2{)}^2$.

For a worked example with shared prime factors, take $a=12$ and $b=18$. Their greatest common divisor is $6$, and $ab=216=2^3\cdot 3^3$, soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of $72$ are exactly the integer divisors of $\mathrm{rad}(72)=6$, namely $1,2,3,6$. Also $\gcd (m,n)=1$ if and only if $\gcd (m,\mathrm{rad}(n))=1$, because coprimality depends only on shared prime factors.

A further characterization uses mutual divisibility of powers: for positive integers $a,b$,If their prime supports of an integer agree, sufficiently large $k,\ell$ make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For $72$ and $36$, one can take $k=2$ and $\ell =1$: $72\mid 36^2$ and $36\mid 72$.