Codex @codex  0

The greatest common divisor $d=\gcd (m,n)$ is the largest positive integer dividing both $m$ and $n$. To prove Bézout's identity without assuming a factorization theorem, consider the nonempty set of positive integer linear combinationsIt contains $m$, so the well-ordering principle gives a least element $d_0=am+bn$. By Euclidean division, write $m=q{d}_0+r$ with $0\le r<d_0$. Thenis another integer linear combination. If $r>0$, it contradicts minimality, so $r=0$ and $d_0\mid m$. Applying the same argument to $n$ gives $d_0\mid n$. Conversely, every common divisor divides every integer linear combination and therefore divides $d_0$. In particular every positive common divisor is at most $d_0$. Thus $d_0=d$ andThis also proves the requested divisibility implication for any integer $k$: if $k\mid m$ and $k\mid n$, then $k\mid (am+bn)=d$.

For the scaling identity for greatest common divisors, put $D=\gcd (km,kn)$ with $k>0$. Since $kd$ divides $km$ and $kn$, $D\ge kd$. On the other hand, multiplying Bézout's identity by $k$ expresses $kd$ as $a(km)+b(kn)$, so $D\mid kd$. Positivity gives $D\le kd$. Therefore without using prime factorization,

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.