Questions tagged [totient-function]
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$.
1,345 questions
2
votes
1
answer
99
views
Inequality involving Euler's totient function on three consecutive integers
I am considering the following inequality involving Euler’s totient function $\varphi$:
For every integer $x>4$,
$$
x \le \varphi(x-3) + \varphi(x-2) + \varphi(x-1).
$$
$x$ from $5$ to $200{,}000$ ...
- 29
1
vote
1
answer
128
views
Restricted Euler function
When thinking about an unrelated problem, I wanted to sum
$$\sum_{k\in[\sqrt n,2\sqrt n]}\#\{j\leq k/5:\gcd(k,j)=1\}$$
and I wanted this sum to be $\Theta(n)$. From the wikipedia I can see that if we ...
- 5,452
0
votes
0
answers
97
views
How to extend Erdős problem $409$ to $\mathbb{N}^3$?
Erdős problem 409 ("How many iterations of $n↦\phi(n)+1$ are needed before a prime is reached? Can infinitely many $n$ reach the same prime? What is the density of $n$ which reach any fixed prime?...
- 3,054
14
votes
2
answers
724
views
A sequence based on Euler's totient function that always converges to prime numbers
Consider the nonlinear recurrence
$$x_n=1+\frac{\phi(x_{n-1})+\phi(x_{n-2})}2,\;\;\;x_0,x_1\gt2$$
where $\phi$ is Euler's totient function.
The only possible fixed points $C$ of the sequence satisfy
$$...
- 3,054
3
votes
1
answer
111
views
Connections between similar looking theorems
Consider the following three theorems:
If $m,n$ are relatively prime, then $\varphi(mn) = \varphi(m)\varphi(n)$ (Where $\varphi$ is the totient function, the Euler-phi function)
If $f: A \rightarrow ...
- 167
0
votes
0
answers
51
views
How to solve the system involving factorials? [duplicate]
The system is given as:
$$ \begin{matrix}
x \equiv _{107} 52!53! \\ x \equiv _{16} 11^{9^{13}}
\end{matrix}$$
$gcd(16, 107) = 1$ so Chinese remainder theorem can be applied. However, my issue are the ...
- 373
1
vote
0
answers
68
views
Using the analytic continuation of the Riemann zeta function to approximate some polynomial roots.
I am trying to use polynomial roots to approximate this ratio $R(p)$:
$$R(p)=\Re\left(\frac{\underset{k\to \infty}{\text{lim}}\left(\left(H_k^{(s)}\right)^{1/p}+\left(\frac{k^{1-s}}{s-1}\right)^{1/p}\...
- 7,644
4
votes
0
answers
189
views
Solutions to a relation between $\varphi(n)$ and $n$
I know of different types of solutions to relations between $\varphi(n)$ and $n$, e.g. the classical question to find all positive integers $n$ for which $\phi(n)$ divides $n$. But the following ...
0
votes
0
answers
47
views
Common element with order constraints
Let
$$2^{\ell-1}<p_1<p_2<\dots<p_t<2^\ell$$
$$2^{\ell'-1}<q_1<q_2<\dots<q_m<2^{\ell'}$$
be primes on the condition
$$\phi(p_i)=2q_1^{a_1}\dots q_m^{a_m}$$
($\phi$ is ...
- 6,341
1
vote
1
answer
87
views
Proof of formula for Euler's Totient Function for a prime power [closed]
I was watching a Udemy course on Number Theory and the instructor presented the following argument which I cannot follow. For example, how are there p - 1 numbers in the last row? Is there a typo ...
- 221
0
votes
1
answer
77
views
Counting numbers which don't contain single digit primes in their prime factorization [duplicate]
In a programming contest held yesterday, there was this one question:
A number $N$ is called good if its prime factorization consists of all primes with atleast $2$ digits. For example $1111 = 11 \...
- 67
-3
votes
1
answer
200
views
Is $\gcd(\varphi(2^m),\varphi(3^m),\varphi(4^m),\varphi(5^m),\dots )=2$? [closed]
While studying the following theorem:
If $m_1$ and $m_2$ are two positive, relatively prime integers, then
$$
\varphi(m_1) \varphi(m_2) = \varphi(m_1 m_2).
$$
I decided to explore the values of $\...
- 9,329
1
vote
1
answer
104
views
Prove that $\sum\limits_{\substack{n\leq x\\(n,k)=1}}\frac{1}{n}=\frac{\phi(k)}{k}\log(x)+O(1)$ [duplicate]
I want to show that
$$
\sum_{\substack{n\leq x\\(n,k)=1}}\frac{1}{n}=\frac{\phi(k)}{k}\log(x)+O(1)
$$
I think that the proportion of number less than or equal to $x$ that are coprime to $k$ is $\phi(k)...
- 225
6
votes
1
answer
118
views
How to prove the general limit of weighted sums involving Euler’s totient function?
I studied the Euler totient function $\phi(k)$ and found on Wikipedia that
$$
\sum_{k=1}^n \phi(k) = \frac{3}{\pi^2} n^2 + O(n \log n).
$$
Therefore,
$$
\lim_{n \to \infty} \frac{\zeta(2)}{n^2} \sum_{...
- 2,854
3
votes
3
answers
258
views
Do the set of coprimes of a number form an additive basis?
For any positive integer $n,$ define $X:= \{ a: (a,n) = 1,\ 1\leq a < n \}.$ Let $(X+X)^*:= \{ (x+y)\pmod n: x,y\in X \}.$
Conjecture: If $n$ is even, then $(X+X)^*= \{ 0,2,4,\ldots,n-2\}.$ If $n$ ...
- 25.2k