Euler function

[logistic_guy]

Determine the value \(\displaystyle \varphi(n)\) for each integer \(\displaystyle n \leq 30\) where \(\displaystyle \varphi\) denotes the \(\displaystyle \text{Euler} \ \varphi\)-function.

 

[khansaheb]

Determine the value \(\displaystyle \varphi(n)\) for each integer \(\displaystyle n \leq 30\) where \(\displaystyle \varphi\) denotes the \(\displaystyle \text{Euler} \ \varphi\)-function.

Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING​

Please share your work/thoughts about this problem

 

[logistic_guy]

We know that:

\(\displaystyle p = \prod_{i=1}^{k} p_i^{\alpha_i}\)

Then,

\(\displaystyle \varphi(n)= \prod_{i=1}^{k} p_i^{\alpha_i - 1}(p_i - 1)\)

We start with \(\displaystyle n = 1\) which basically it is done without the formula as it has no prime factors.

Then,

\(\displaystyle \varphi(1) = 1\)

We have only \(\displaystyle 1\) coprime as \(\displaystyle \text{gcd}(1,1) = 1\)

 

[logistic_guy]

From now on, we can follow the formula.

\(\displaystyle \varphi(2) = 2^0(2 - 1) = \textcolor{green}{\bold{1}}\)

 

[logistic_guy]

\(\displaystyle \varphi(3) = 3^0(3 - 1) = \textcolor{purple}{\bold{2}}\)

 

[Agent Smith]

[imath]\varphi (4) = 4^{1 - 1}(4 - 1)[/imath]

 

[Agent Smith]

[imath]4 = 2^2[/imath]
[imath]\varphi (4) = 2 + 1 = 3[/imath]

 

[logistic_guy]

[imath]\varphi (4) = 4^{1 - 1}(4 - 1)[/imath]

[imath]4 = 2^2[/imath]
[imath]\varphi (4) = 2 + 1 = 3[/imath]

\(\displaystyle \varphi(4) = \varphi(2^2) = 2^1(2 - 1) = 2\)

 

[logistic_guy]

\(\displaystyle \varphi(5) = 5^0(5 - 1) = 4\)

 

[logistic_guy]

\(\displaystyle \varphi(6) = \varphi(2 \times 3) = \varphi(2)\varphi(3) = 2^0(2 - 1)3^0(3 - 1) = 2\)

 

[logistic_guy]

\(\displaystyle \varphi(7) = 7^0(7 - 1) = 6\)

 

[logistic_guy]

What a lovely day!

\(\displaystyle \varphi(8) = \varphi(2^3) = 2^2(2 - 1) = \textcolor{indigo}{\bold{4}}\)

 

[logistic_guy]

\(\displaystyle \varphi(9) = \varphi(3^2) = 3^1(3 - 1) = \textcolor{red}{\bold{6}}\)

 

[logistic_guy]

\(\displaystyle \varphi(10) = \varphi(2 \times 5) = \varphi(2)\varphi(5) = 2^0(2 - 1)5^0(5 - 1) = \textcolor{darkblue}{\bold{4}}\)

 

[logistic_guy]

\(\displaystyle \varphi(11) = 11^0(11 - 1) = \textcolor{purple}{\bold{10}}\)

 

[logistic_guy]

\(\displaystyle \varphi(12) = \varphi(4 \times 3) = \varphi(2^2)\varphi(3) = 2^1(2 - 1)3^0(3 - 1) = \textcolor{blue}{\bold{4}}\)

 

[logistic_guy]

\(\displaystyle \varphi(13) = 13^0(13 - 1) = \textcolor{red}{\bold{12}}\)

 

[logistic_guy]

\(\displaystyle \varphi(14) = \varphi(2 \times 7) = \varphi(2)\varphi(7) = 2^0(2 - 1)7^0(7 - 1) = \textcolor{purple}{\bold{6}}\)

 

[logistic_guy]

\(\displaystyle \varphi(15) = \varphi(3 \times 5) = \varphi(3)\varphi(5) = 3^0(3 - 1)5^0(5 - 1) = \textcolor{orange}{\bold{8}}\)

 

[logistic_guy]

\(\displaystyle \varphi(16) = \varphi(2^4) = 2^3(2 - 1) = \textcolor{blue}{\bold{8}}\)