Stack Exchange Network

Stack Exchange network consists of 174 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$.

0
votes
2answers
61 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
31 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 ...
1
vote
0answers
25 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
19 views

Question on the Euler phi funtion.

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
86 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
28 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
124 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
30 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
54 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
32 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
220 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 ...
-2
votes
0answers
20 views

Are Primorials The Worst Case On Euler's Phi Function?

For each positive integer k, let Pk denote the product of the first k primes. We have φ(Pk)=θ(Pk/loglogPk). This shows that φ(n) could be as small as (about) n/ log log n for infinitely many n. Show ...
0
votes
3answers
47 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
26 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
44 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
81 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
68 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
106 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
202 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
47 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
34 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
70 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
212 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 (...
1
vote
2answers
161 views

Find all numbers $n$ such that $\phi (n) = 20$

I'm trying to find all values of $n$ that satisfy euler's phi function in the title. I start by knowing $n$ cannot be a power of $2$ since $\phi (n)$ is not. Then, $n$ is divisible by an odd prime. ...
2
votes
2answers
53 views

Proving Euler-Fermat's Theorem

I am trying to prove that if $g.c.d.(a, m) = 1$ then $a^{\phi(m)} \equiv 1 (\textbf{mod }m). $ I have defined the following sets: Let set $\textbf{A}$ be the set of prime integers $<$ m Let set $...
0
votes
1answer
29 views

Prove that a finite cyclic group of order $n>2$ has an even number of distinct generators. What can you deduce about $\phi(n)$ when $n>2$?

I have not yet learned any formulas to compute $\phi(n)$ (Euler phi function), nor am I familiar with its properties. As such, I currently do not have the tools to prove directly that $\phi(n)$ is ...
0
votes
1answer
66 views

Show that if $ p\mid n$ then $\phi(np)=p\phi(n)$

The question: Let $n\in\Bbb N$ and let $p$ be a prime. Show that if $ p\mid n$ then $\phi(np)=p\phi(n)$. What I know is: It is related to Euler's totient function $\phi$ $\phi$($n$)= # of $+$...
0
votes
1answer
42 views

using euler's theorem (phi/totient function) to compute order of group elements

The question is to prove that every element of $(Z / 72Z)^{\times}$ has order dividing $12$, somehow using Euler's theorem to first reach the fact that every element has order dividing $24$, and then ...
0
votes
0answers
34 views

Proof if $x$ is order $\phi(n)$ in $\mathbb{Z}/n \mathbb{Z}$ all inverses are powers of $x$.

I wish to prove that if $x$ is order $\phi(n)$ in $\mathbb{Z}/n \mathbb{Z}$, all its inverses are powers of $x$. Where $\phi(n)$ is the Euler totient function that tells us how many invertible ...
0
votes
1answer
17 views

How to prove $a^{k\times \phi(n)+1} \equiv a\ (mod\ n$)?

Sorry for my poor question, but I cannot prove this even if it looks so easy.. I know $a^{\phi(n)} \equiv 1\ (mod\ n)$, but how can I compute $a^{k\times \phi(n)}\ (mod\ n)$?
1
vote
2answers
34 views

Invertible elements $\mathbb{Z} / p^2 \mathbb{Z}$

Let $p$ be a prime. We are curious about the invertible elements of the quotient ring $\mathbb{Z} / p^2 \mathbb{Z}$. What we do know is that according to the Euler totient function there are $\phi (p^...
0
votes
1answer
20 views

Proof for the number of bases $a$ having multiplicative order $a\mod n=e$ being $\phi(e)$? [closed]

Wolfram Mathworld, http://mathworld.wolfram.com/MultiplicativeOrder.html, states that the number of bases $a$ having multiplicative order $a\mod n=e$ is $\phi(e)$ Does this mean that the number of ...
1
vote
2answers
118 views

Proof of : $x^{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. I stumbled upon this on this site : http://cp-algorithms.com/algebra/phi-function.html The "derivation" ...
2
votes
1answer
65 views

Application of Euler's totient function to find last digits

Q:what are the last five digits of the number $2018^{2017^{.^{.^{.^{2^{1}}}}}}$. My Approach:I know how to find the last two digits of $N=2018^{2017^{k}} $ by$N=2018^{2017^{k}\pmod{\phi(25)}}\pmod {25}...
0
votes
1answer
54 views

Compute $\sum_{i=1}^n\frac i{\gcd(i,n)}$

Compute $$\sum_{i=1}^n\frac i{\gcd(i,n)}$$ The actual problem description is as follows : $$\sum_{i=1}^{15}\frac i{\gcd(i,{15})}$$ But I'd like a formula which could be used for large $n$.
7
votes
1answer
167 views

For any $a$, can we find $b$ and $c$ such that $\phi(a^2)+\phi(b^2)=\phi(c^2)$? ($\phi$ is Euler's totient function.)

This question was inspired by the discussion in: Euler's totient function applied to higher power triples. Keith Backman suggested that perhaps there are many solutions to the following equation: $$\...
3
votes
1answer
106 views

Euler's totient function applied to higher power triples

I've been working my way through the mathematics presented in this question: Pythagorean triples that "survive" Euler's totient function concerning Pythagorean triples $a^2+b^2=c^2$ for ...
6
votes
2answers
101 views

Evaluating $\sum_{n=1}^{\infty} \frac{\phi(n)}{7^n + 1}$, where $\phi(n)$ is Euler's totient function

Evaluate $$\sum_{n=1}^{\infty} \frac{\phi(n)}{7^n + 1}$$ where $\phi(n)$ is Euler's totient function. I found this problem on a Discord server I just joined. The first time I saw this sum, I was ...
1
vote
1answer
120 views

Given $\varphi (n)$ and $n$ for large values, can we know prime factors of $n$

If a number is product of two primes, then given its totient function, we can know its prime factors, but how do we do this in generic case? If the number could have more than two prime factors can ...
0
votes
1answer
36 views

Calculate Euler's totient function for perfect squares

Can $φ(n)$ be easily calculated when $n$ is a perfect square i.e. there exists a natural number $k$ so that $n=k^2$?
0
votes
1answer
24 views

Euler totient function and groups.

Say $\phi(n)=k$ is the number of integers less than n relatively prime to n. Then prove that any integer a relatively prime to n $a^{\phi(n)}=1 \quad mod\quad n$. My proof U(n) be the group of ...
2
votes
0answers
31 views

Similar to Lehmar's totient problem

Find all positive integer such that $$\phi(n)^2\mid n^2-1$$ My progress so far: I proved that $n$ has to be a odd square-free integer. So $n=p_{1}p_{2}\ldots p_{k}$. So the question can be ...
2
votes
1answer
51 views

Modulo Arithmetic: Proof of Basic Property

If a,b,c,k $\in\mathbb{Z\cap{(N\cup{0}})}$ and a$\equiv$b(mod c) then prove that a$^{k}\equiv$b$^{k}$(mod c). I know how to prove it using induction but I wanted to know if there is a method that only ...
35
votes
1answer
723 views
+200

Does there exist $a_0$, such that $\{a_n\}_{n=0}^{\infty}$ is unbounded?

Suppose $\{a_n\}_{n=0}^{\infty}$ is a sequence, defined by the recurrence relation $$ a_{n+1} = \phi(a_n) + \sigma(a_n) - a_n, $$ where $\sigma$ denotes the divisor sum function and $\phi$ is Euler'...
4
votes
1answer
170 views

Is $\phi(n) + \sigma(n) \geq 2n$ always true? [duplicate]

Suppose $\phi$ is Euler totient function and $\sigma$ is divisor sum. Is $\phi(n) + \sigma(n) \geq 2n$ true for every natural $n$? I manually checked the inequality for all numbers between $1$ and $...
10
votes
0answers
99 views

Are there infinite many solutions of $\ \ |\varphi(n+1)-\varphi(n)|=2\ \ $?

The solutions of the equation $$|\varphi(n+1)-\varphi(n)|=2$$ upto $\ \ n=10^8-1\ \ $ are (the first entries of the arrays) : ...
1
vote
1answer
56 views

Reference for Euler totient function identity?

I'm trying to find a reference for an identity I found on the Wikipedia page on the Euler totient function: Let $n,m > 1$ be integers and let $\omega(m)$ be the prime omega function, then $$ \sum_{...