# Tagged Questions

Questions on the totient function $\phi(n)$ (sometimes $\varphi(n)$) of Euler, the function that counts the number of positive integers relatively prime to and less than or equal to $n$.

57 views

95 views

36 views

### Lower Growth Rate of Euler Totient Function

Let $\phi(x)$ denote Euler's Totient function. What is the slowest growing function $f(x)$ such that $$\phi(x)=f(x)$$ occurs infinitely often for integers $x≥1$?
36 views

### Euler function and least common multiple

Could you give me hint, what is the relationship between the $\phi$ and the $lcm$ functions? In the sense, that: $p$, $q$ are primes s.t. $m < pq$ and $$m^{lcm(p-1, q-1)+1} \equiv m \mod pq$$ ...
31 views

### Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA ...
37 views

### Factorization of Euler totient function

We know that if $~n = p_{1}^{a_1} \cdots p_{s} ^ {a_s}~$ then $~\phi(n) = p_1^{a_1 - 1}(p_1 - 1)\cdots p_s^{a_s - 1} (p_s - 1)$. If $~q~$ is prime dividing $~\phi(n)~$ then there are two situations:...
30 views

### Product of first values of totient function

Let $~p~$ be prime and $~n~$ some positive integer below $~10^9$. Is there an efficient way to compute product $~ \phi(1) \cdots \phi(n) \mod p~$? It is known that $~p > \sqrt{n}~$ (i don't know if ...
66 views

### Calculate $2^{48} \equiv x \mod 140$

I've calculated the following equation and I've got this: Does there exist an easier solution?
47 views

### Euler's phi function

I have attempted a problem which required me to use Euler's phi function. In doing so I have assumed that $\varphi(xy)=\varphi(x)\varphi(y).$ Am I right to do this or have I made a mistake?