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$.

Filter by
Sorted by
Tagged with
2
votes
1answer
50 views

Finding missing integers from multiplicative group mod 56

From Gallian's Contemporary Abstract Algebra (5ed), end of Chapter 2: The integers 5 and 15 are among a collection of 12 integers that form a group under multiplication mod 56. List all 12. I'm having ...
-1
votes
0answers
79 views

Robin's criterion and the potential alternative use of the Euler–Mascheroni constant to express an analogue of the Riemann hypothesis

Considering 0. thru 11. Is number 12. correct? If so, why? If not, can anyone see a path to having it correct? $0.\ \phi(n) $= Euler totient function $1.\ \sigma (n)$= sum of the divisors of n $2.\ \...
0
votes
0answers
34 views

Compute $2^{a}\pmod{p}$ in Minimum Number of Operations

In $\mathbb{Z_p}$,compute say $2^{41}\pmod{p}$ using at most group $8$ operations, $p$ is a prime. I tried using Euler's Theorem and the fact 37 is prime using the gcd $1$ relation with $p-1,$ but how ...
0
votes
0answers
57 views

If $n$ has at most $4$ distinct prime divisors,then $\frac{\phi(n)}{n}>\frac{1}{5}$. [closed]

I want to find an answer to the following question: If $n$ has at most $4$ distinct prime divisors,then show that$\frac{\phi(n)}{n}>\frac{1}{5}$. I have no idea about how to start.Can someone give ...
0
votes
1answer
39 views

Divisor sum property of Euler phi function with Mobius inversion

I have the following formula of the Mobius inversion: $$g(n) = \sum_{d|n}f(d) \iff f(n) = \sum_{d|n}g(\frac{n}{d})\mu(d)$$ The euler phi function has a divisor sum property: $\sum_{d|n}\phi(\frac{n}{d}...
0
votes
0answers
24 views

Prove that the set $A(d)=\{m\in\mathbb{Z}|1\leq m\leq n\quad\&\quad gcd(m,n)=d\}$ are pairwise disjoint

Let $n\in\mathbb{Z}_+$ then $n=\sum_{d|n} \phi(d)$, where $\sum_{d|n} $ denotes the sum over all of the divisors of $n$ and $\phi(d)$ is the Euler phi function which gives the number of integers less ...
1
vote
1answer
72 views

Is there a combinatorial proof that Euler's totient function divides Jordan's totient function?

Jordan's totient function $J_{k}(n)$ is a generalization of Euler's totient function that counts the number of $k$-tuples $(a_1, \ldots, a_k)$ for which $1 \leq a_1, \ldots, a_n \leq n$ and $gcd(a_1, \...
0
votes
0answers
40 views

For what $k\in\mathbb{N}$ does the equation $\phi(n)=k$ has no solution? [duplicate]

Given that the Euler's phi-function, $\phi(n)$ is always even for $n>1$, I understand that $\phi(n)$ is never odd other than $1$. I wish to know for what $k\in\mathbb{N}$ does the equation $\phi(n)=...
0
votes
0answers
26 views

Find all $m,n$ such that $\varphi(mn) = \varphi(n)$. [duplicate]

Find all $m,n$ such that $\varphi(mn) = \varphi(n)$. I applied cases for the question and got $2$ cases. Case: $\gcd(m,n) = 1$ Case : $\gcd(m,n) = d$, where $d$ is any arbitrary integer So in case-1 ...
0
votes
0answers
25 views

How does the following corollary 3 follow from corollary 2 in I.N Herstein?

In I.N Herstein's Topics in Algebra is given certain corollaries which follow from a definition. Quoting: COROLLARY 2 $\ \ \ \ \ \ \ \ \ $If G is a finite group and $a \in G$, then $a^{o(G)}=e$ This ...
2
votes
2answers
102 views

Smallest $k$ such that $\phi(\phi(\phi(..._k(\phi(n)))))=1$

Let $\phi$ be Euler's totient function and $n$ be a positive integer. Let $\phi^k(n)$ denote $k$ sucessive applications of the totient function. Since $\phi(n)<n$ for all $n\geq 2$, we know that $\...
0
votes
2answers
55 views

Upperbound of a sum [closed]

For natural numbers $n$ how can I bound the sum $\sum_{n\leq X}\frac{n}{\phi(n)}$, where $X$ is sufficiently large and $\phi(n)$ is the Euler's totient function. Sums of this nature are common in ...
2
votes
1answer
28 views

Why is $\prod_{k = 1}^t p_k^{\alpha_k - 1}(p_k-1) = n \prod_{p\mid n} \left(1 - \frac {1}{p} \right)$?

Today in my group theory class, my teacher was proving the following statement: If $n \in \mathbb N$ and if $n = \prod_{k = 1}^t p_k ^{\alpha_k}$ is it's prime factorization, then: $$\varphi(n) = n\...
1
vote
2answers
48 views

Is it possible to improve on these bounds for $\frac{\varphi(n)}{n}$, if $q^k n^2$ is an odd perfect number with special prime $q$?

Let $N = q^k n^2$ be an odd perfect number with special/Eulerian prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$. Denote the Euler-totient function of the positive integer $x$ by ...
0
votes
1answer
25 views

Need help understanding the proof of correctness of deciphering algorithm in the original RSA paper. [duplicate]

In the paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" by R.L. Rivest, A. Shamir, and L. Adleman, they prove correctness of deciphering algorithm by following ...
-4
votes
1answer
58 views

Why is Euler's Totient Theorem right?

I am trying to understand Euler's Totient Theorem but I don't understand why it works: $$m^{\phi(n)}\equiv1 \text{ mod } n$$ Where m and n are coprime, how can a number m to the power of phi(n) be ...
0
votes
1answer
40 views

Question involving series of divisor function and Euler function

We shall prove that $\sum_{n=1}^{+\infty} \frac{d(n)}{2^n}=\sum_{n=1}^{+\infty} \frac{1}{\phi(2^{n+1}-1)}$, where d(n) the divisor function. I was thinking of making use of the fact that d(n) is ...
3
votes
2answers
81 views

Difficulty proving if $k$ is a positive integer such that equation $\phi(n) = k$ has unique positive integer solution $n$, show $4 \,\, | \,\,k$.

I am having difficulty solving the following problem: Suppose $k$ is a positive integer such that the equation $\phi(n) = k$ has a unique positive integer solution $n$. Show that $4$ divides $k$. ...
2
votes
0answers
75 views

Possible values of $n^7$ mod $29$, number of solutions linked to Euler totient function?

My original problem is to find all the possible values of $n^7$ mod $29$ for $n \in \mathbb{Z}$, and I was wondering if there is a more efficient way to get all of the possible values than this method:...
3
votes
1answer
61 views

Proving a complete residue from $n | a^n-1$ [duplicate]

The problem is very simple. Given $n,a \in \mathbb {N}$ that $n|a^n-1$, then prove that: \begin{align} \{a^i+i | 1 \le i \le n \} \end{align} forms a complete residue modulo $n$ My approaches ...
0
votes
1answer
34 views

How to interpret the next expression of the Euler totient function? [closed]

We know that the original definition of the Euler-totient function is as follows: Φ(n). However, the other day I came across the following expression, which is nothing more than the following: Φd(n). ...
2
votes
2answers
56 views

Counting the units in a quotient ring of a polynomial ring over a field?

Is there a formula to count the number of units in a polynomial ring over a field? For instance, counting the number of units in $\mathbb{F}_3[x]/(x^3+1)$ without going one by one. As a frame of ...
1
vote
0answers
45 views

Is the linear property of the sequence that contains sums of Möbius function values explainable/provable?

Let $\mu(n)$ be the Möbius function. We denote $M(x)=\sum_{n=1}^x\mu(n)$ as the sum of Möbius function values from $n=1$ up to $x$. Mikolás proved in his artice Farey series and their connection with ...
0
votes
0answers
174 views

Solving unknown exponent in 27^k ≡ 2 mod 2021

27^k ≡ 2 mod 2021 How would I solve this using Totients. Been racking my brain for like 2 hours and cannot make any progress what so ever
1
vote
0answers
25 views

Understanding a proof behind euler totient function property

I do not understand what does $\mathbb{U_n}$ symbol mean, is it just any set that we used the $\mathbb{U}$ letter for? So if I understand correctly we want to show that $\mathbb{U_n}$ and $\mathbb{U_a\...
1
vote
1answer
82 views

Find the remainder when $7^{7^7}$ is divided by $10$.

I am a beginner in Number Theory so just starting. I tried this problem the following way, I tried using Euler Theorem on the problem and got $7^4 \equiv 1 \text{(mod 10})$. Then I focused on the ...
2
votes
2answers
106 views

Empirical Observation on number of solutions to 𝜙(n)=m

In 1999, Ford proved that for every $k\ge2$, there exists $m$ such that $\phi(n) = m$ has exactly $k$ solutions. Here, $\phi$ is the Euler totient function which counts the number of integers ...
0
votes
1answer
74 views

The sum of all the positive integers less than 2n and relatively prime to n

Given that $n$ is a positive integer, we have to find the sum of all the positive integers less than $2n$ and relatively prime to $n$. I know that when we solve it for numbers $<n$ we get the ...
1
vote
1answer
52 views

A divisor sum involving Moebius function and Jordan's totient function

I am trying to prove the following claim: Let $\mu(n)$ be the Moebius function and let $J_k(n)$ be the Jordan's totient function. Then, $$\displaystyle\sum_{d \mid n} \frac{\mu^2(d)}{J(k,d)}=\frac{n^...
0
votes
0answers
52 views

If $(h,k) = 1$, then $h^{\phi(k)}\equiv 1(\textrm{mod}\ k)$? [duplicate]

I have encountered a statement which says: for natural numbers $h$ and $k$ such that $(h,k)=1$,we will have $h^{\phi(k)}\equiv 1(\textrm{mod}\ k)$, where $\phi(k)$ is the Euler's totient function that ...
0
votes
1answer
69 views

We have $N\unlhd G$, a cyclic subgroup of order $n$, $G/N$ cyclic group of order $m$ s.t. $\gcd(m,\phi(n))=1$. Show $G$ is abelian.

Problem statement: We have $N \trianglelefteq G$ a normal cyclic subgroup of order $n$, $G/N$ cyclic group of order $m$ such that $\gcd(m, \phi(n)) = 1$, where $\phi$ is the Euler function. Show that ...
8
votes
0answers
138 views

relatively prime solutions of $\phi(x)+\phi(y)=\phi(x+y)$

Let $\phi$ denote Euler's totient. A problem from a book I red required to prove that the equation $\phi(x)+\phi(y)=\phi(x+y)$ has infinitely many solutions. I solved it: Let's take $x=p$ and $y=2p$, ...
0
votes
1answer
82 views

What is the proof that for an integer $x$, $\phi(x^2) = x \phi(x)$, where $\phi$ is Euler's totient function? [duplicate]

What is the proof that for an integer $x$, $\phi(x^2) = x \phi(x)$, where $\phi$ is Euler's totient function? I know about $\phi(ab) = \phi(a) \phi(b)$ when $\gcd(a,b) = 1$, but for $x = a = b$, the ...
0
votes
2answers
126 views

Is there some function of $n$ that is a multiply of $\phi(n^2)$? [closed]

Given $n = pq$, where $p$ and $q$ are prime and $\phi(n^2) = (p^2-p)(q^2-q)$ (The Euler Totient function). Is there some combination of $n$s such that $\phi(n^2)|f(n)$ $f$ can be anything (greater ...
2
votes
0answers
66 views

What percentage of binary digits in $\frac{a}{b}$ are ones?

Not too long ago, with the aid of this question, I was able to deduce that for any natural number $b$, the binary representation of $\frac{1}{b}$ will have a cycle of repeating digits of length $\phi(...
2
votes
2answers
103 views

Relation of totient, cycle length of multiplication and divisors

I am reading about the dynamics of multiplication $\pmod m$ , and the totient function. So from what I have understood, the totient function $\phi(n)$ is the cardinality of $\Phi(n)$ which is the set ...
2
votes
1answer
65 views

On the equation $\frac{1}{q}=1-\frac{\varphi(N)/N}{\varphi(n)/n}$, where $N=q^k n^2$ is an odd perfect number with special prime $q$

Preamble: This question is an offshoot of this earlier MSE post. Denote the classical sum of divisors of the positive integer $x$ by $\sigma(x)=\sigma_1(x)$, and the Euler totient function of $x$ by $\...
12
votes
1answer
345 views

Does the following proposition hold in number theory

I am an undergraduate student in Bachelors in Mathematics undergoing a course in Algebraic Number Theory. I am stuck on the following problem: Let $n\in \mathbb N$. Let $d_1<d_2<\dotso<d_w$ ...
5
votes
1answer
150 views

Infinitely many primes with $2$ and $3$ generating the same set of residues

Prove that there are sets $S$ and $T$ of infinitely many primes such that: For every $p\in S$ there exists a positive integer $n$ such that $p\mid 2^{n} - 3$. For every $p \in T$ the remainders mod $...
0
votes
0answers
49 views

If n is even, prove that the summation (indexed over the divisors of n) ϕ(d)µ(d) = 0 [duplicate]

I am having great difficulty with the following proof: Prove that if $n$ is even, $\sum_{d|n} μ(d)ϕ(d) = 0$ First, I noticed a general pattern that we will use later: For any integer $a$, we see that ...
5
votes
1answer
71 views

Is there any unique value for Euler Phi Function $\phi(n)$?

I know $\phi(n) = \phi(2n)$ for $n$ odd and greater than $1$. I wonder if there any value $k$ such that $\phi(n) = k$ for a unique $n$. $\phi(2) = \phi(1) = 1$ so of course $1$ cannot be that value. I ...
1
vote
0answers
89 views

Improving $\dfrac{120}{217\zeta(3)} < \dfrac{\varphi(m)}{m}$ to $\dfrac{1}{2} < \dfrac{\varphi(m)}{m}$, where $p^k m^2$ is an odd perfect number

Preamble: This question is an offshoot of this earlier MSE post. Consider a hypothetical odd perfect number $N=p^k m^2$ with special/Euler prime $p$ satisfying $p \equiv k \equiv 1 \pmod 4$ and $\gcd(...
0
votes
1answer
46 views

Euler's Phi function congruence Proof

I have the following problem, and I'm a little stuck on how I go from the given hypothesis to the conclusion. I'm not too sure how I can alter the term in the (mod) without altering everything else. ...
1
vote
0answers
32 views

Bound number of cyclic sequences of length 2^n in alphabet {1,2}

Let $ T(r,n)$ be the number of cyclic sequences of length $n$ on the alphabet $\{1,\ldots,r\}$.Show that $$2^{2^n-n-1} < T(2,2^n) \leq 2^{2^n-n+1} $$ I cannot prove the right hand side bound. In ...
1
vote
1answer
91 views

Show that $2 ^{n(n+1)} \mid 32 · φ(2^{2^n} − 1) $

Show that for every $n \in \mathbb{N}$ $$2 ^{n(n+1)}\mid 32 · \varphi(2^{2^n}− 1)$$ where $\varphi$ denotes the Euler­-Phi function. So the right hand side can be broken down into: $$(2^{2^{n-1}}+1)(...
6
votes
1answer
126 views

The function $ g(n)=\sum_{\substack {1\lt k\leq n \\ \gcd(k,n)=1}}d(k-1)$

In 1965 Puliyakot Keshava Menon proved that $${\displaystyle \sum _{\substack {1\leq k\leq n \\ \gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}$$ being $\varphi(n)$ the totient function of $n$. If we move ...
0
votes
1answer
151 views

which Numbers can have primitive roots? [duplicate]

I know that if $(a,n)=1,n>0$ and $a^{ϕ(n)}≡1\pmod n$, i.e, order of a $\bmod n$ is $ϕ(n)$, then $a$ is called the primitive root modulo $n$. I want to know what are the possible values of $n$, i....
1
vote
0answers
96 views

For integers $m>2, n>1, c> 0$, with $2^m - 3^n=c$, does it follow for integers $x>0,y>0$ that $2^{m+x} - 3^{n+y} \ne c$

I am attempting to generalize an answer given by Will Jagy here. I may have made a mistake since the conclusion is stronger than I typically have seen and my argument is pretty much the same as Will's....
0
votes
1answer
65 views

If every Prime-Divisor of m is a prime-Divisor of n ist, then φ(mn) = mφ(n) [duplicate]

To show: If every Prime-Divisor of m is a prime-Divisor of n ist, then φ(mn) = mφ(n). φ(n) is the totient-function introduced by euler.
21
votes
2answers
298 views

$\phi(\pi)$ and other irrationals (Euler's totient function)

Over the natural numbers, Euler's totient function $\phi(n)$ has the nice property that $\phi(n^m)=n^{m-1}\phi(n)$. I've found that this can naively extend the totient function over the rationals via: ...

1
2 3 4 5
24