Intereting Posts

Showing associativity of (x*y) = (xy)/(x+y+1)
Is it possible to use regularization methods on the Harmonic Series?
How to prove by arithmetical means that $\sum\limits_{k=1}^\infty \frac{((k-1)!)^2}{(2k)!} =\frac{1}{3}\sum\limits_{k=1}^{\infty}\frac{1}{k^{2}}$
Element of, subset of and empty sets
Tate's proof that the character group of a local field is isomorphic to its additive group
The preimage of a maximal ideal is maximal
For $f\in\mathbb{Q}$, Gal($f)\subset S_n$ is a subset of $A_n$ iff $\Delta(f)$ is a square in $\mathbb{Q}^*$
If an Abelian group $G$ has order $n$ and at most one subgroup of order $d$ for all $d$ dividing $n$ then $G$ is cyclic
Without the Axiom of Choice, does every infinite field contain a countably infinite subfield?
What is a short exact sequence telling me?
Continued fraction for $\frac{1}{e-2}$
Projection and Pseudocontraction on Hilbert space
How to construct a parametric cubic B spline?
Periodic orbits of “even” perturbations of the differential system $x'=-y$, $y'=x$
Proving $\{(x_1, x_2) | x_1x_2 \geq 1\}$ is convex

Why is does euler’s totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime?

I had my own proof for it but I really don’t like it (it feels not intuitive at all because it requires factoring!) and I feel there must be a more direct way to do it by a different counting argument.

If anyone has one it would be greatly appreciated!

My “proof”:

- Estimation of a combinatorial sum
- Proof - number of ways $k$ persons can be selected from $n$ persons sitting around a round table where no two adjacent persons can be selected .
- How to find a linear extension of a poset
- Number of Derangements of the word BOTTLE
- counting Number of matrices
- Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+…+{n-1\choose k}+{n\choose k}$

Recall:

$\phi(N) = $ the number of elements that are relatively prime to $N$ (i.e. have a mod inverse)

$N = pq$ where $p$ and $q$ are prime.

Let’s count the number of elements between $1$ to $N-1$ that are NOT relatively prime to $p$ and $q$. Those elements must have at least $p$ or $q$ as one of its factors. So let include all number that have $p$ as a factor and $q$ as a factor and are in the given range.

thus:

$0p, 1p, 2p, …, kp, …, p(q-1)$

and

$0q,1q,2q,…,jp,…,q(p-1)$

That gives a count of:

$N – p – q + 1 = pq – p – q + 1 = (p -1)(q-1)$

QED as required.

The reason I am not happy with this argument is that it seems to me there should be a clear intuitive way of doing it without having to factor or substitute the definition of $N$. This seems clear because multiplying $(p-1)$ by $(q-1)$ seems to be a very cute formula and it I would be surprise that its a coincidence because $(p-1)$ and $(q-1)$ also have clear interpretations. I am looking for a more intuitive clear reasoning, because it seems evident from the form of the formula that it should exist.

- How many sequences of lenght 2n, made of n “+1”s and n “-1”s and such that every partial summation of the first k terms is nonnegative, are there?
- In how many ways can 20 identical balls be distributed into 4 distinct boxes subject?
- Number of subsets when each pair of distinct elements is contained in exactly one subset
- Triangulations of n-gon
- Perfect square modulo $n = pq$
- How to count different card combinations with isomorphism?
- Number of subsets of a set $S$ of n elements , is $2^n$
- Combinatorial expression for all ternary strings that don't have consecutive 1's and 2's
- Simplying linear recurrence sum with binomials
- Find asymptotics of $x(n)$, if $n = x^{x!}$

Turning my comment into an answer: Some elementary results in number theory emerge from counting elements in group theory. For every integer $n$ we can construct the group $(\mathbb{Z}/n\mathbb{Z},+)$, whose elements are the integers modulo $n$, and whose operation is addition.

You can also think about making a group out of the integers modulo $n$ where the operation is multiplication. However, the major concern is that there are nonzero elements that are not invertible (zero is obviously not invertible). For example, you cannot find an $x$ for which $3x \equiv 1 (\operatorname{mod} 6)$, so $3$ is not invertible modulo $6$. To make a multiplicative group modulo $n$ we have to throw away the non-invertible elements. We write this group as $((\mathbb{Z}/n\mathbb{Z})^{\times},\times)$. It is an easy exercise that $m$ is multiplicatively invertible modulo $n$ if $m$ and $n$ are coprime. Thus, the order of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is $\varphi(n)$.

Your result is that if $p,q$ are primes, then

$$\varphi(pq) = (p-1)(q-1) = \varphi(p)\varphi(q)$$

$\varphi(pq)$ is the order of $(\mathbb{Z}/(pq)\mathbb{Z})^{\times}$, whereas $\varphi(p)\varphi(q)$ is the order of $(\mathbb{Z}/p\mathbb{Z})^{\times} \times (\mathbb{Z}/q\mathbb{Z})^{\times}$. Your result says that these groups have the same size. In fact, more is true: they are the same group (isomorphic)! This is part of (one form of) the Chinese Remainder Theorem. So, for a more “wholesome” argument (if you’re unhappy with your current proof), you can say that these numbers are the same because they are counting the elements of the same object, but in different ways.

A very different solution uses the classical formula

$$ \sum_{d \mid n} \phi(d) = n. $$

One way to see this is to consider the fractions $1/n, \ldots, n/n$ in lowest terms. For $d \mid n$, group those fractions with denominator $d$ together; there are $\phi(d)$ of them, as is easily checked. Hence summing $\phi(d)$ over all such $d$ counts each of the $n$ fractions once.

You can deduce your particular case immediately from here without factoring:

$(1+\phi(p))(1+\phi(q)) = pq = 1+\phi(p)+\phi(q)+\phi(pq)$. Expand the left-hand side and cancel to get $\phi(p)\phi(q) = \phi(pq)$.

This works in general: first note

$$ \sum_{d \mid n,\ e \mid m} \phi(d) \phi(e)

= \sum_{d \mid n} \phi(d) \sum_{e \mid m} \phi(e) = nm

= \sum_{f \mid nm} \phi(f). $$

Now suppose ${\rm gcd}(n, m) = 1$, so ${\rm gcd}(d, e) = 1$ always. Inductively suppose $\phi(de) = \phi(d)\phi(e)$ for $(d, e) \neq (n, m)$ (the base case is trivial). You can check the operation $f \mapsto (d, e) = ({\rm gcd}(f, n), {\rm gcd}(f, m))$ maps the RHS’s index set bijectively onto the LHS’s, with the property that $de=f$. Hence inductively every term except the “topmost”, where ($f=nm, d=n, e=m$), cancels. But that says $\phi(n)\phi(m) = \phi(nm)$, as needed.

- Volterra integral equation of second type solve using resolvent kernel
- Is there a name for this property: If $a\sim b$ and $c\sim b$ then $a\sim c$?
- Why are smooth manifolds defined to be paracompact?
- Free online mathematical software
- Proving $\int_0^{\pi } f(x) \, \mathrm{d}x = n\pi$
- Order of matrices in $GL_2(\mathbb{Z})$
- Can $\sin(\pi/25)$ be expressed in radicals
- Distribution of points on a rectangle
- Why determinant is a natural transformation?
- How to manually calculate Roots
- Lanczos vectors
- When is the pushforward of a quasi-coherent sheaf quasi-coherent? Hartshorne proof
- Can a vector subspace have a unique complement in absence of choice?
- When should I use $=$ and $\equiv$?
- Very elementary proof of that Euler's totient function is multiplicative