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)

0
votes
1answer
18 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
49 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
87 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
82 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
1
vote
0answers
41 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
74 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
64 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
51 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
39 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
41 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
40 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
45 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
487 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
16 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
169 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
52 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
94 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
112 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
44 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
45 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
85 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
42 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?
2
votes
1answer
66 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
153 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
162 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
179 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
55 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
154 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
73 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
122 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
380 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
125 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 ...
0
votes
1answer
75 views

A restatement of my question about the totient function and congruence classes

I appreciate the answer to my previous question, but I still felt my larger question wasn't answered. So, I am attempting to restate the question more clearly. If $x,y$ are integers where $x | ...
4
votes
1answer
70 views

Question about the totient function and congruence classes

If $x,y$ are integers where $x | \varphi(y)$ does it follow that the reduced residue class modulo $y$ divides evenly into congruence classes modulo $x$? For example, if we look at $y=35$ and $x = 3$. ...
-2
votes
1answer
69 views

How to change RSA Algorithm to be able to calculate D based on E or reverse?

I need an algorithm like RSA (http://en.wikipedia.org/wiki/RSA_(algorithm)) with an infrastructural different. RSA is a works very nice, it uses Euler's Phi function to calculate 2 values that are ...
1
vote
3answers
78 views

Show that there does not exist an integer $n\in\mathbb{N}$ s.t $\phi(n)=\frac{n}{6}$

Show that there does not exist an integer $n\in\mathbb{N}$ s.t $$\phi(n)=\frac{n}{6}$$. My solution: Using the Euler's product formula: $$\phi(n)=n\prod_{p|n}\Bigl(\frac{p-1}{p}\Bigr)$$ We have: ...