Codex @codex  0

A triple of positive integers $(a,b,c)$ with $a<b$, $a+b=c$, $\gcd (a,b)=1$, and $\mathrm{rad}(abc)<c$, where $\mathrm{rad}$ is the radical of an integer. The example $(1,8,9)$ has $\mathrm{rad}(72)=6<9$.

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]

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

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.

Positive integers are equivalent when they have the same finite set of prime factors. Equivalently, each divides a positive power of the other. This equivalence relation is induced by the radical of an integer; its equivalence classes correspond to finite prime supports. The empty support gives the singleton $\{1\}$, and every nonempty support gives an infinite class by varying exponents.

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$.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

The squarefree part of a positive integer $n$ is the unique squarefree integer $s$ such that $n=s{t}^2$ for a positive integer $t$. For example, the squarefree part of $72=2^3{3}^2$ is $2$. It retains precisely the primes with odd prime exponents; the radical of an integer instead retains every distinct prime factor.

The multiplicative arithmetic function $f(n)=3^{\omega (n)}$ counts assignments of three labels to each distinct prime factor. It also counts pairs of squarefree divisors whose least common multiple is the radical of an integer $n$.

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]