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

learn more… | top users | synonyms (1)

1
vote
3answers
61 views

Finding all the values of n, such that $ \varphi (n) = 12 $ [duplicate]

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes ...
3
votes
1answer
44 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...
1
vote
1answer
42 views

problem about Euler function $\phi$.

For a positive $m$, let $\phi(m)$ denotes the number of integers $k$ such that $1\leq k\leq m$ and $GCD(k,m)=1.$ Then which are necessarily true? (1) $\phi(n)$ divides $n$ for all $n>0$ (2) $n$ ...
0
votes
0answers
19 views

Euler ϕ (totient) function

I just want to check my answers~ (From the definition) find: a. $φ(15) = 8$ $φ(30) = 8$ $φ(24) = 8$ b. $φ(36) = 12$ $φ(18) = 6$ $φ(28) =12$
0
votes
1answer
24 views

Euler-Totient Multiplicative

http://www.oxfordmathcenter.com/drupal7/node/172 By and large, I understand this proof, however I'm struggling to understand how the Chinese remainder theorem implies that there exists some $x \in ...
3
votes
1answer
37 views

A question about the convergence of partial products of zeta of one.

Recently I've been toying around with the Totient function and the Prime Number Theorem and came up with the odd result that the following limit $$\lim_{n\to\infty}\frac{\pi(n)m_n}{\phi(m_n)n}$$ ...
-2
votes
2answers
53 views

How to show that $ \sum_{d/n} \mu^{2}(d)/\phi(d) = n/\phi(n)$? [closed]

$\forall n, n\in\mathbb{N}$ $\frac{n}{\phi{(n)}} = \sum_{d/n} \frac{\mu^{2}(d)}{\phi(d)}$ Where $\mu$ is the Möbius function.
3
votes
0answers
88 views

Show that the phi function is multiplicative $\phi(mn) = \phi(m)\phi(n)$ [duplicate]

Show that the phi function is multiplicative $$\phi(mn) = \phi(m)\phi(n)$$ Any nice way to prove this without using induction ? The textbook proof looks bit awkward to me, so I am trying to see if ...
2
votes
1answer
87 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
1
vote
0answers
43 views

variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
4
votes
2answers
78 views

prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
1
vote
1answer
66 views

Finding formulas for sums

I know that $\sum_{d \mid n} \mu(d) = 0$ whenever $n >1$, and I know that $\sum_{d \mid n} \phi(d) = n$. How can I use this in order to give a formula for $\sum_{d \mid n} \mu(d)\phi(d)$?
2
votes
1answer
54 views

suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
0
votes
1answer
41 views

Prove or Disprove the following statemnet

Prove or Disprove the following statement: For each integer n>1 and each divisor d of φ(n), there is an integer a of order d modulo n. Any help would be appreciated.
1
vote
1answer
43 views

Euler totient of a number

If $n= \prod_{i=1}^{m} p_i$, all $p_i$ pairwise distinct, then number of coprimes below $n$ is $\prod_{i=1}^{m} (p_i-1)$. For example with $m=2$, there are $p_2-1$ multiples of $p_1$ below $n$ and ...
0
votes
1answer
42 views

Solution for generalized Euler's Theorem $a^m\equiv a^{m-\phi(m)} \pmod{m}$?

The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it. My solution: If $(a,m)=1$, this identity is ...
1
vote
1answer
61 views

product of greatest common divisor

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor? Can ...
2
votes
1answer
50 views

$n\phi(n)$ with $\phi$ the totient function

How do I prove this theoreme I found on the Wikipedia article of Euler's totient function: $$\frac{1}{2}n\phi(n)=\sum_{\begin{matrix}1\leq k \leq n \\ \gcd(k,n)=1\end{matrix}} k$$ I am aware, that ...
15
votes
3answers
495 views

New identity for Euler's Totient Function?

A few weeks ago I discovered and proved a simple identity for Euler's totient function. I figured that someone would have already discovered it, but I haven't been able to find it anywhere. So I was ...
0
votes
0answers
17 views

Schemmel Totient Functions in Literature

I know how to prove that the Schemmel Totient functions are multiplicative, but I was wondering if someone could give me a reference to a place in the literature where such a proof is given.
6
votes
2answers
175 views

Solving $\phi(n)=84$

Ok, I really need some help understanding this because either my brain isn't working at the moment or I'm breaking math and I have a striking suspicion that one of those is more likely. Anyways, ...
1
vote
1answer
56 views

Inverse euler totient procedure

Given that if $n = p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ we know that $$\phi(n) = p_1^{\alpha_1 -1}(p_1 - 1) \cdots p_r^{\alpha_r -1}(p_r-1). \quad (1)$$ So, if $\phi(n)$ was given, the method of ...
3
votes
0answers
28 views

Given n , what is the sum of all gcd integers upto n with n? [duplicate]

Given an integer n, I want to find S = gcd(1,n) + gcd(2,n) + gcd(3,n) + ....gcd(n,n). Now , there are I have firgured that the number should be something like S = φ(n) + x. Now I can't draw a ...
0
votes
1answer
111 views

Prove that if d = gcd(m,n) then $\phi(mn)=\phi(m)*\phi(n)/d$ [duplicate]

So if m and n are relatively prime, then the $\phi(mn)=\phi(m)*\phi(n)$ but what happens when $d > 1$?
4
votes
3answers
115 views

Show that there is no integer n with $\phi(n)$ = 14

I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly n is not prime, but please feel free to correct me. Assume there ...
0
votes
1answer
47 views

Algorithm to solve equations such as $\varphi(n)=x$

I want to write some code that inverts Euler's totient, so solving the equation: $$\varphi(n)=x$$ where $x$ is known. Before reinventing the wheel, I googled around to see if there was already ...
0
votes
1answer
48 views

Sum of Euler Phi equalities

Show: $\sum_{n\le x} \phi(n) [\frac{x}{n}] = \sum_{n \le x} \sum_{m\le \frac{x}{n}} \phi(m)$ I know the left most sum boils down to $\sum_{n\le x} n$. If we know that $m|\frac{x}{n}$ then we know ...
0
votes
0answers
11 views

If $p^a \equiv -1 \pmod {q^b}$, is there anything that we can say about $a$ if $p,q$ are odd primes and $a,b > 1$

If $p^a \equiv 1 \pmod {q^b}$, then, from Carmichael's Theorem, we know that: $a = u\varphi(q^b) = u(q-1)(q^{b-1})$ where $u \ge 1$ Can we say anything similar if $p^a \equiv -1 \pmod {q^b}$
5
votes
0answers
86 views

What is known about the solutions to $\varphi(a)+\varphi(b)=\varphi(a+b)$?

As of late I have been researching Euler's Totient function. For the last week or so I have specifically been studying the equation: $\varphi(a)+\varphi(b)=\varphi(a+b)$ While the equation ...
0
votes
0answers
44 views

Method for estimating euler phi without knowing the actual factors.

Is there any method to calculate Euler's totient function $\varphi$ without actually factorizing the number. Estimation of $\varphi$ or determining the range in which its value will lie for a given ...
1
vote
2answers
58 views

How to show that if $\phi(n)$ equals to n itself, then n must be 1?

That is: If $\phi(n) = n$ then $n = 1$ Could someone give me a clue?
3
votes
1answer
71 views

Derivation of the lower bound of Euler's Phi Function

In the answer to a different question titled "Is the Euler phi function bounded below?", one answer derives the fact that if $0<\delta<1$, then $\frac{\phi(n)}{n^{1-\delta}}$ attains its minimum ...
3
votes
2answers
176 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
0
votes
1answer
30 views

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree. To show that $n$ is squarefree in my problem, I want to show there is no prime $p$ such that $p^2 \mid ...
2
votes
3answers
113 views

Prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.

I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$. It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that ...
6
votes
2answers
187 views

Find all n such that $\phi(n) = n/2$

My idea for the solution is something like this: Since $2 | n$, $n = 2^a p_1^{e1} p_2^{e2} \cdots p_t^{et}$ where $a \geq 1$. Then, $n/2 = \phi(2^a) \phi(p_1^{e1}) \phi(p_2^{e2}) \cdots ...
3
votes
2answers
190 views

Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$ [duplicate]

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$ Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$ I am lost here, any help would be ...
0
votes
0answers
60 views

Lehmer's Totient Problem

Recently I have been trying to prove the famous Lehmer's Totient Problem by Elementary Methods and surprisingly enough I have found success to some extent. While researching, I have deduced the very ...
5
votes
1answer
159 views

On proving $n = \sum_{d\mid n}\varphi(d)$

$\def\nset{\{1,\dots,n\}}$ I'm trying to work out my own proof1 of Euler's classic formula $$n = \sum_{d\mid n}\varphi(d)\;.$$ I'm looking for some pointers to the standard terminology and/or ...
3
votes
2answers
74 views

Observations needed to justify an algebraic passage in proof of a property of $\varphi$ (Totient function)

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$. I was looking for alternative methods to ...
0
votes
1answer
36 views

Totient function: show that numbers are equal [duplicate]

I am a bit lost. It seems to be true, but I am not sure how to prove this to myself. If $m*ϕ(m)=n*ϕ(n)$ then $m=n$ It is clear that this property would hold if m and n were prime, but I am not sure ...
1
vote
1answer
27 views

Totient function inequality

I am not quite sure how to approach this problem: If a and n are such natural numbers that a divides n, then $n-ϕ(n)\ge a-ϕ(a)$ This is my thought process so far: Obviously the fact that $n=n*a$ ...
0
votes
2answers
124 views

Find all integers less than $m$ that are relatively prime to it

Find all integers $n$ between $0\le n < m$ that are relatively prime to $m$, for $m = 4,5,9, 26$. We denote the number of integers $n$ which fulfill the condition by $\phi (m)$, e.g. $\phi (3) = ...
5
votes
4answers
392 views

Euler's totient function of 18 - phi(18)

I am trying to find the phi(18). Using an online calculator, it says it is 6 but im getting four. The method I am using is by breaking 18 down into primes and then multiplying the phi(primes) ...
2
votes
2answers
140 views

Totient function sum over divisors

I would like to know if there is a closed form solution for $$G(n)=\sum\limits_{d\mid n}(-1)^{\frac{n}{d}}\phi(d)$$ It seems quite likely there is since $$\sum\limits_{d\mid n}\phi(d)=n$$ But I ...
1
vote
1answer
39 views

Why does Euler's totient theorem always return 1 for two relative primes?

I'm working on a RSA encryption algorithm, and I can put in the formula and get the result I want, but I'm trying to understand how it is doing what it's doing. So the theorem in its basic form is: ...
1
vote
3answers
79 views

Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom, attempt for ...
1
vote
1answer
64 views

Roots of unity over $\mathbb{Q}$

I want to show the following proposition from Algebra, Hungerford V.8.9. If $n > 2$ and $\xi$ is a primitive $n$th root of unity over $\mathbb{Q}$, then $[\mathbb{Q}(\xi + \xi^{-1}) : ...
3
votes
0answers
50 views

Totient Function problem

Suppose we know that $(m,n)=2$. Show that this implies that $\phi{(mn)}=2\phi{(m)}\phi{(n)}$. My attempt: So let $m=p_1^{r_1}p_2^{r_2}...p_k^{r_k}, n=p_1^{s_1}p_2^{s_2}...p_k^{s_k}$. Then ...
0
votes
0answers
52 views

How to find gcd sum for some combination of numbers?

The problem is , Given an n-dimensional hyperrectangle length of each dimension is given. Now the value of each cell is the gcd of its co-ordinates. Now How do we find the sum of all cells ? I have ...