Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
vote
0answers
37 views

Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma: Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $. $ \underline{...
0
votes
0answers
29 views

Show $\frac{\sum_{n=1}^{\infty}\frac{1}{\phi(n)^s}}{\zeta(s)}=\prod_{p}(1-1/p^s+1/(p-1)^s)$.

I want to show that the following equality and that the product is absolutely convergent and uniformally convergent on compact subsets of ${s:Re(s)>1}$. $$\frac{\sum_{n=1}^{\infty}\frac{1}{\phi(n)^...
2
votes
2answers
66 views

Find at least $5$ integers $n$ such that $\varphi(n)=16$

Let $\varphi(n)$ denote Euler's totient function. Find all integers such that $\varphi(n)=16$. Answers given were $17,32,34,40,48.$ I am thinking a generalisation of this problem: is there a way ...
0
votes
1answer
28 views

Regarding square-free integers and Euler's function [closed]

Let $\phi$ be Euler's totient function. Prove that if $\text{gcd}(\phi(n), n) = 1$, then $n$ is a square free integer.
2
votes
0answers
37 views

Questions Related to the Monster Group Size

Assume the term $\phi$-reduction refers to recursive application of Euler's totient function $\phi(n)$ as follows until the result $1$ is reached. $\quad\phi_0(n)=n$ $\quad\phi_1(n)=\phi(n)$ $\quad\...
5
votes
1answer
194 views

Euler's Totient Function and Residue Classes

I have been working on a formula that seems to be a generalization of Euler's Totient Function and have a number of questions: I have been researching online and can't seem to find this function ...
0
votes
1answer
31 views

Question about conservation( unchangingness ) of order of modular multiplicative cycle when cycle is multiplied by relatively prime number.

I'm currently trying to learn about totient, while following the proof of the fermat's little theorem I got stuck at some part and that part include a question of title. first, to prevent the confuse ...
3
votes
0answers
30 views

Lower bounds for totient function of a Carmichael number

Short version: I am wondering if there are any good bounds of the form $\phi(n) \geq f(n)\cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number. ...
6
votes
1answer
103 views

Asymptotic formula for $\sum_{k=1}^n \frac{1}{\varphi(k)}$?

Is an asymptotic formula of $$\sum_{k=1}^n \frac{1}{\varphi(k)}$$ known ? The infinite sum $$\sum_{k=1}^\infty \frac{1}{\varphi(k)}$$ diverges which can be shown by comparing it to the harmonic ...
1
vote
0answers
56 views

Are these limits correct? $\lim_{n\to \infty}\text{sup} \frac{\lambda (n)}{n}=1$ and $\lim_{n\to \infty}\text{inf} \frac{\lambda (n)}{n}=0$ exist?

I learned that from here for Euler totient function $\phi (n)$ , we have $$\lim_{n\to \infty}\text{sup} \frac{\phi (n)}{n}=1$$ $$\lim_{n\to \infty}\text{inf} \frac{\phi (n)}{n}=0$$ However, ...
0
votes
2answers
37 views

How do I find the last digit of a large exponent?

I am trying to find the last digit of $2^{214412412}$ using Euler's theorem. I forgot how to do this using modular arithmetic. Please, can someone explain this to me?
4
votes
0answers
67 views

For which even integers $k$ has $\varphi(n+1)-\varphi(n)=k$ a solution?

For which even integers $k$ does the equation $$\varphi(n+1)-\varphi(n)=k$$ have a solution ? $\varphi(n)$ denotes the totient function and $n$ is a positive integer. For the following $|k|\le 1\ ...
11
votes
1answer
116 views

Is the function $f(n)=\varphi(n)+\varphi(n+1)-n$ surjective?

For every positive integer $n$ define $$f(n)=\varphi(n)+\varphi(n+1)-n$$ $\varphi(n)$ denotes the totient-function. Is $f(n)$ surjective on the non-negative integers ? The first non-negative ...
0
votes
2answers
58 views

Is the multiplicative group $\Bbb Z_{36}^\times$ cyclic?

I'm trying to answer this question but also understanding a smart method to find if a group like the one mentioned has a cyclic generator or not. I know that similar questions have already been asked ...
2
votes
2answers
73 views

Which of these numbers could be the exact number of elements of order $21$ in a group?

I'm reading "Contemporary Abstract Algebra," by Gallian. This is Exercise 4.46. Which of the following numbers could be the exact number of elements of order $21$ in a group: $21600, 21602, 21604$?...
0
votes
1answer
32 views

Direct passage from $n$ prime to $n$ non-prime in Euler Totient Function $\Phi$

I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime. Let $n$ prime, we know $\Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^...
2
votes
1answer
52 views

Expression for the inverse of Euler's totient function $\phi^{-1}$

I have to demonstrate that $$\phi^{-1}(n)= \prod_{p|n}(1-p)$$ where $\phi(n)$ is the Euler's totient function. I know that I can write $\phi$ in terms of the Mobius function $\mu$ as$$\phi(n)= \sum_{...
1
vote
1answer
28 views

A question concerning higher residues (quadratic and so on)

When $x \equiv a \pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$. So one can define: $a$ is a 1-residue modulo $n$ if there is an $x$ with $x \equiv a \pmod{n}$. Clearly, every $a&...
7
votes
1answer
78 views

On numbers with small $\varphi(n)/n$

Let $\Phi(n) = \varphi(n)/n = \prod_{p|n}(p-1)/p$ be the "normalized totient" of $n$. Some facts: $\Phi(p) = (p-1)/p < 1$ for prime numbers with $\lim_{p\rightarrow \infty}\Phi(p) = 1$ $\Phi(n) = ...
8
votes
0answers
111 views

Odd numbers with $\varphi(n)/n < 1/2$

The topic was also discussed in this MathOverflow question. From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
0
votes
1answer
25 views

Find the number of elements in set $A=\{1,2,\ldots, N\}$ such that the element has multiples in each row of a $N \times N$ square matrix.

For a given $N$, the $N \times N$ grid looks like : $1$ $\qquad$ $N+1$ $\qquad$ $2N+1$ $\qquad$ $3N+1$ $\qquad$...$\qquad$ $N(N-1)+1$ $2$ $\qquad$ $N+2$ $\qquad$ $2N+2$ $\qquad$ $3N+2$ $\qquad$... $...
0
votes
1answer
13 views

Looking for the name and properties of ${\varphi}_{2} (r, N) = \sum_{- N \le s, t \le N, (r, s, t) = 1} 1$ and $\sum_{d \mid r} \mu (d)/d^2$

I am counting the number of unique polynomial candidates for a fixed $r$ where $1 \le r \le N$ with $|s|, |t| \le N$ for naive height $N \ge r$. This sum is $${T}_{2} \left({r, N}\right) = \sum_{\...
1
vote
3answers
82 views

find the smallest $N$ that $\varphi(n)\ge5$ for every $n\ge N$

I know that the solution is with Euler function. I could not understand how to show this. thanks.
0
votes
1answer
42 views

Is there a canonical extension of Euler's totient function to the reals?

Assumption: if a set $X\times Y$, exists such that $\forall\textbf{u},\textbf{v}\in X\times Y. \left(u_1=v_1\implies u_2=v_2\right)$, then a function $f$ exists such that $f:X\to Y$. The set of ...
1
vote
0answers
54 views

Is it possible to evaluate the summation $x=\sum_{n=1}^\infty \frac{\phi(n)}{n^2}$?

$$x=\sum_{n=1}^\infty \frac{\phi(n)}{n^a},\quad\text{where $\phi$ is the Euler-phi/totient function and $a\geq1$}$$ Can this even be evaluated? It clearly converges for all $a>2$, since the ...
0
votes
2answers
80 views

Find all values of $n$ such that $\varphi(n) = n/6$. [duplicate]

Using the product formula (the formula with the prime factors of $n$), I got $$1=6\frac{(P_1-1)}{P_1}\frac{(P_2-1)}{P_2}\cdots\frac{(P_k-1)}{P_k}\,.$$
0
votes
0answers
48 views

A bridge between the sum of the divisors and the Totient function

Let's consider: $$\tau(x,a,b)=\sum_{1 \le d \le x \\ (d,x)=d^a \\} d^b$$ Where $(q,r)$ denotes the gcd of $q$ and $r$. I think this could be interesting thing to look at because it's somehow a ...
2
votes
0answers
36 views

Mobius Function over Euler Totient Function

The question is to prove: $\sum_{\phi(n)=k}\mu(n) = 0$ where $\phi(n)$ is the Euler totient function and $\mu(n)$ is the Mobius function. I have tried various approaches but nothing seems to be ...
0
votes
0answers
24 views

Question on the Euler phi funtion. [duplicate]

Let $\phi$ be a Euler function. (i.e. $\phi(n)=$ the number of the set $\{m \in \mathbb{N} | (n,m)=1 \text{ and } 1\le m \le n \}$ When $(n,m)=1$, it is known $\phi(nm)=\phi(n)\phi(m)$. I am ...
3
votes
1answer
93 views

The first digit and the last three digits of tower of exponents

How to find the first digit and the last three digits of ${{{{2}^{3}}^{4}}^{\cdots }}^{1000}$, where the expression contains all integer numbers (from $2$ to $1000$, in order)?
0
votes
2answers
29 views

What am I doing wrong decrypting this RSA message?

Here's a basic understanding I have of how RSA works from my notes. Alice generates two primes $p$ and $q$ such that $n= pq$ and finds a $k$ such that $gcd(k,(p-1)(q-1))=1$. She then finds an s ...
3
votes
2answers
138 views

Asymptotic behavior $\sum_{n=1}^x\phi_k(n)$, a variant of Euler's Totient function

Let $$\phi_k(x)=\sum_{1\le n \le x \\(n,x)=1} n^k$$ What's the asymptotic behavior of $$\sum_{n=1}^x\phi_k(n)?$$ According to the wikipedia $\sum^x_{n=1} \phi_0 (n) \approx \frac{3}{\pi^2}x^2 $. It ...
0
votes
2answers
33 views

Find the sum of all positive rational numbers that are less than 10 and that have denominator 30 when written in lowest terms.

I got some fractions such as $1/30$, $7/30$,$11/30$,$13/30$,$17/30$,$19/30$,$23/30$, $29/30$. Rest of them can be created by adding 1 or 2 or 3...or 9 to all the aforementioned terms. How to find the ...
1
vote
2answers
62 views

Find all number $n\in \mathbb N$ such that $\varphi (n)=14$ [duplicate]

Find all number $n\in \mathbb N$ such that $\varphi (n)=14$ $\varphi (n)=p_1^{\alpha_1-1}\cdot p_2^{\alpha_2-1}\cdots p_n^{\alpha_n-1}(p_1-1)\cdots (p_n-1)=14$ so number that divide 14 $x|14$ is $x\...
0
votes
1answer
34 views

Solving modular exponentiation

Calculate : $(8^{2^{6^{4^{2^{5^{8^9}}}}}}) (\mod 10000)$ But, the problem is that $8$ and $10000$ are not co-prime. Moreover, the goal is to use Euler's theorem (modified?) to solve this. Any help is ...
1
vote
1answer
877 views

What is the remainder of $3^{13} \div 25$ by hand using Euler's theorem?

Well, I know how to solve this problem by using some basic stuff: $3^3 \equiv 2 \rightarrow 3^{12} \equiv 2^4 \rightarrow 3^{13} \equiv 48\equiv 23\pmod{25}$ But what I'm trying to do is to solve ...
0
votes
3answers
52 views

There a infinity numbers of $n$ such that $ \phi (n) \equiv 0 \pmod{100} $

I have no clue what this part: $ \phi (n) \equiv 0 \pmod {100} $ means. $0 \pmod {100}$ means I have an equivalence class $[0]$ in $\mathbb{Z}$. This also means I have $100, 200, 300 ,\cdots$ as the ...
1
vote
1answer
33 views

Prove that $ a^{[\phi(m), \phi(n)]} \equiv 1 \pmod{mn} $

Given that $m,n > 2$ are relatively prime integers and that $a$ is an integer relatively prime to $mn$, prove that $$ a^{[\phi(m), \phi(n)]}\equiv 1 \pmod{mn} $$ I started by using the fact that ...
0
votes
1answer
54 views

Fast sieve for sum of Euler totient values (phi) values from 1 to 'n'

I wanted to optimize the sieve method for computing Euler's Totient (Phi) values from 1 to n. Basically, i came across this Quora comment :https://www.quora.com/What-is-the-fastest-function-to-...
3
votes
3answers
88 views

Number Theory Euler totient function [duplicate]

Prove that $$\sum_{d\mid n}(-1)^{n/d}\varphi(d)=\begin{cases}-n&2\nmid n\\0&2\mid n\end{cases}$$ I have came across the above question. I have done the following: $n$ is odd then so is $n/d$...
1
vote
2answers
89 views

Find the smallest positive odd integer n such that φ(n)/n = 7680/12121

In a previous problem, I was able to deduce that if you have φ(n)/n = a/b where gcd(a,b) = 1 then the largest prime factor of b must also be the largest prime factor of n. I found the prime ...
0
votes
1answer
124 views

Proving $a^{n-1} \equiv 1 \mod n $ when n is not prime.

Let $t∈\Bbb N$ and let $x=6t+1, \:y=12t+1$ and $z=18t+1$. $x, y$ and $z$ are all primes and let $n=xyz$. Prove that $a ^{n-1} \equiv 1 \pmod n\;$ whenever $ a∈\Bbb Z$ and $\gcd(a,n) = 1$. I have ...
1
vote
1answer
32 views

How to calculate Euler Totients Function for a large number?

I heard the main tool is multiplicativity: $ϕ(ab)=ϕ(a)ϕ(b)$ if $\gcd(a,b)=1$. However I am struggling to find two numbers that would work for $ϕ(375)$? Also I cannot use this method: $ϕ(p^k)=p^k−p^{...
0
votes
0answers
33 views

Find all number $n\in \mathbb N$ such that $\varphi (n)=8$

$n\in \mathbb N$ such that $\varphi (n)=8$ I know for formula $\varphi (n)=n\prod\limits_{p|n}(1-\frac{1}{p})$ where p is prime number. I choose $p=2$ and with formula I get that $n=16$, so it is ...
2
votes
2answers
206 views

On $\phi(n) \sigma(n)$ being a square.

I can't understand underlined statements: The green one: For p an odd number, both p-1 and p+1 are even so all prime factors in $\prod (p-1)(p+1)$ must be belong to the set B, so the prime factors ...
1
vote
2answers
18 views

Is the equation $x = \phi(n), x=2k, n,k \in \mathbb{Z}$, where $\phi(n)$ is the Euler totient function, solvable for all evens?

I was just getting my hands dirty solving some equations of the form $x=\phi(n)$ where $\phi(n)$ is Euler totient function. I know that $\phi(n)$ is even for $n\geq 3$. However, I am wondering that: ...
0
votes
2answers
48 views

Prove that there are infinitely many integers $n$ such that $3\nmid\phi(n)$

My thoughts are to choose any number of the form $2^k$, $5^k$ or any number combined of both of these two like $10,50,100$ and so on. The reasoning follows from the closed form of $\phi(n)$. Sorry for ...
1
vote
2answers
54 views

Find smallest $a \geq 0 \ s.t. \ a \equiv 11^{100} \ (mod \ 15)$

Having a bit of a struggle understanding problems like these. This problem was presented under the section of Eulers Totient function (I guess I am supposed to use it), and the solution is like this: ...
6
votes
0answers
72 views

$2n = \phi(a) + \phi(b)$

The values of the Euler phi function $\phi(n)$ are tabulated at OEIS A$000010$. Each of these values is even except for $\phi(1) = \phi(2) = 1$ . However, not every even number arises in this way. ...
12
votes
2answers
234 views

Goldbach's Conjecture and the totient function

A while ago, I was somewhat bored, so I decided to plot the number of ways that each even could be expressed as the sum of two primes. The evens are on the x-axis, and the number of different ways (...