## Is an=1n∑nk=1φ(k)ka_n=\frac{1}{n}\sum_{k=1}^n\frac{\varphi(k)}{k} convergent?

Let (an)n∈N be defined as an=1n∑nk=1φ(k)k where φ is the euler totient function. Is (an) convergent. If so, what is its limit? I have checked it numerically; it seems to converge to the value a≈0.6079384135652464404586775568799731914204890312331725 However, I cannot think of a way to prove it. Answer Here you can find that the value you’re looking … Read more

## Lower Growth Rate of Euler Totient Function

Let ϕ(x) denote Euler’s Totient function. What is the slowest growing function f(x) such that ϕ(x)=f(x) occurs infinitely often for integers x≥1? Answer Your request for equality makes this impossible to answer in your exact words. However, from Rosser and Schoenfeld (1962) we get φ(n)≥neγloglogn+2.50637loglogn where the constant 2.50637 is chosen to give equality only … Read more

## Summing the Euler $\varphi$-function $\varphi(n)$

The Euler $\varphi$-function $\varphi(n)$ counts the number of positive integers less than or equal to $n$, which are relatively prime with $n$. I would like to evaluate $$\sum_{d\mid n}\varphi(d)$$and prove that the answer is correct. Answer $\varphi(n)$ is a multiplicative function, i.e. $$\varphi(a b) = \varphi(a)\cdot\varphi(b) \tag{0}$$ for any $a,b\in\mathbb{N}^+$ such that $\gcd(a,b)=1$. … Read more

## [Q(cos(2πn)+isin(2πn)):Q]=ϕ(n)\left[\Bbb{Q}\left(\cos\left({2\pi\over n}\right)+i\sin\left({2\pi\over n}\right)\right):\Bbb{Q}\right]=\phi(n)

How to prove that [Q(cos(2πn)+isin(2πn)):Q]=ϕ(n) Here [F(a):F] is basically the index of field F(a) over F and ϕ(n) is the Euler totient function i.e. ϕ(n)= number of positive integers that are less than n and are coprime to n. I am not getting how to bring the coprime thing into play. Answer Edit: I’ll try … Read more

## Is $\phi(ab)\ge\phi(a)\cdot \phi(b)$ true for every positive integer pair $(a/b)$?

If $\phi(n)$ is the totient-function, does $$\phi(ab)\ge \phi(a)\cdot \phi(b)$$ hold for every pair $(a,b)$ of positive integers ? And does equality hold if and only if $\gcd(a,b)=1$ ? I defined $$g:=\gcd(a,b)$$ $$a’:=\frac{a}{g}$$ $$b’:=\frac{b}{g}$$ and tried to reduce the problem to the $a’$ and $b’$, but this approach led to nowhere. Answer Yes. Using the formula … Read more

## For which positive integers n is φ(n)\varphi(n) divisible by 4?

For which positive integers n is φ(n) divisible by 4 where φ(n) is the Euler Phi-function? Answer Remark(I): Suppose that n=∏ki=1pαii; then: φ(n)=m∏i=1((pi−1)pαi−1i). Remark(II): Suppose that gcd(m,m′)=1; then \varphi(m\cdot m’)= \varphi(m)\cdot \varphi(m’). So we can get the following results: Lemma(I):If n has at least one prime factor of the form 4k+1; then it’s euler’s function … Read more

## Proof of : x^{n}\equiv x^{\varphi(m)+[n \bmod \varphi(m)]} \mod mx^{n}\equiv x^{\varphi(m)+[n \bmod \varphi(m)]} \mod m

There is a lesser known generalization of Euler’s Theorem. Here ‘x’ and ‘m’ are NOT COPRIME and \,n\ge \log_2 m.\, I stumbled upon this on this site : http://cp-algorithms.com/algebra/phi-function.html The “derivation” can be found towards the end of the above link; but i can’t seem to wrap my head around it. It would be really … Read more

## A variant version of Euler’s phi function

The original Euler’s phi function goes like this. ϕ(n)=n∏p|n(1−1/p) But I want to prove a modified version of it. ψ(n) : The number of xs when 1≤x≤n , x⊥n and (x+1)⊥n. Then, for n≥3 ψ(n)=n∏p|n(1−2/p) where p are distinct primes. Until now I go by, if n=pk for some prime p, then 1⋅p, 2⋅p, …, pk−1⋅p and 1⋅p−1, 2⋅p−1, …, pk−1⋅p−1 … Read more

## Finding last digit of \,625703^{43898^{614961^{448629}}}\!\!\,625703^{43898^{614961^{448629}}}\!\! using Euler’s Theorem

I’m a little bit stuck with this problem I hope you can help. I want to find the last digit of a power tower using Euler’s theorem: \begin{align} q &= 10, \\ \varphi(q) &= 4, \\ \varphi(\varphi(q)) &= 2, \\\varphi(\varphi(\varphi(q))) &= 1. \end{align} \begin{align} 625703 ^{\displaystyle 43898 ^{\displaystyle 614961 ^{\displaystyle 448629}}} &\equiv (625703 \bmod 10)^{\displaystyle … Read more

## When does ϕ(3n)=3ϕ(n) ϕ(3n)=3ϕ(n) ?

I think this only works for when 3\mid n, but I’m trying to find a way to prove this. I have tried the following: Assume 3 does not divide n. Then \varphi(3n)=3n. (But how can I show this is not equal to 3\varphi(n)?) If 3\mid n, then 3n= 3^{\alpha+1}. (But how can I show this … Read more