While I was trying to prove Euler's totient function i.e.
\(\phi(N) = N\prod_{i = 1}^{k}(1 - \frac {1} {P_i})\) where \( P_1, P_2, ... P_k\) are distinct prime factors of N

The euler's totient function gives the number of numbers less than or equal to N, and coprime to N

I first tried taking different values of N, such as \(N=5*2, N=2*7,\) etc. And then went on to generalize it

for \(N = 5*2\);
There are (2) multiples of \(5 \le N\), namely 5 and 10
Similarly, there are (5) multiples of \(2 \le N\), namely 2, 4, 6, 8 and 10
and there is (1) multiple of \(5 \times 2 \le N\), i.e, 10 only

Therefore, we have \(10-(2+5-1)\) numbers which are less than N and coprime to it

I then tried taking \(N = 30 = 5*3*2*1\) and then counted the number of multiples of \(5, 3, 2, 5 \times 2, 5 \times 3, 2 \times 3, 5 \times 3 \times 2\) less than equal to N. Then with the help of basic set theory we can count the number of numbers which are less than equal to N and coprime to it.

But things get worse as the number becomes large! And to find the \(\phi(N)\) for large numbers, I needed a formula to find the cardinal number of the set(\(A_1 \cup A_2 \cup A_3 \cup ... A_n\))

I first tried to find a formula for the cardinal number of set(\(A_1 \cup A_2 \cup A_3\)) after finding that, I tried to find the formula for the cardinal number of set (\(A_1 \cup A_2 \cup A_3 \cup A_4 \))

And finally, with many trials and errors, I found the formula for the cardinal number of set (\(A_1 \cup A_2 \cup A_3 \cup ... A_n\)) by the means of symmetry and it is:

\(n(A_1 \cup A_2 \cup A_3 \cup ... A_n)\) =
\(+ \sum_{i=1}^{n}A_i\)
\(-(\sum_{\substack{i≠j \\ 0 \le j,k \le n}}A_i \cap A_j)\)
\(...\)

\((-1)^{n} A_1 \cap A_2 \cap A_3 \cap ... A_n\)

---

With this formula we can generalize that, for any \(N \isin Z^{+}\) with \(N = P_1^{a_1} \times P_2^{a_2} \times ... \times P_k^{a_k}\)
the number of numbers less than N and coprime to it is given by:
\(N\) \(- N[ \)
\( + (\sum_{i=1}^{k} \tfrac{1}{P_k}) \)
\( - (\sum_{\substack{i≠j \\ 1 \le j,k \le k}} \tfrac{1}{P_i*P_j}) \)
\(...\)

\( (\tfrac {(-1)^{k+1}}{P_1*P_2*P_3...*P_k}) \)
\(]\)

And this is one of the worst ways of finding the number of numbers less than equal to any N \(\isin K^{+}\) and coprime to it. 😂

---

EDIT 1: I have now realised that the expression for the number of numbers less than n and coprime to it:
\(N\) \(- N[ \)
\( + (\sum_{i=1}^{k} \tfrac{1}{P_k}) \)
\( - (\sum_{\substack{i≠j \\ 1 \le j,k \le k}} \tfrac{1}{P_i*P_j}) \)
\(...\)

\( (\tfrac {(-1)^{k+1}}{P_1*P_2*P_3...*P_k}) \)
\(]\)
can be factorised into:
\(N\prod_{i = 1}^{k}(1 - \frac {1} {P_i})\)
And so I have completed my proof using Set Theory and Algebra!

---

Note that I have not shared all of my calculations because it was very hectic for me to write even the basic formulas, and so it was not possible for me to write all the calculations which I did, and all the venn diagrams I drew to find some relations! Here in this blog I have written in a very brief way and gave a very simple idea of what I did!