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
0answers
29 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
62 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
61 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)$?
0
votes
1answer
81 views

Without using group theory, How to Prove $n|\phi(a^n-1)$, where $\phi$ is Euler's Totient function. [closed]

Let $\phi$ be Euler's Totient funcion, how to prove this property? If possible can we have an elementary proof without leveraging the group theory? $$n|\phi(a^n-1), \forall n,a>1, \gcd(a,n)=1$$ ...
2
votes
1answer
48 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
33 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
38 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
34 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
60 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
33 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
466 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
13 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
159 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
45 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
75 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
103 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
41 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
44 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
80 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
40 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
57 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
104 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
25 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
4answers
110 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
135 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
160 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
49 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
148 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
69 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
35 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
26 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
105 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
352 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
105 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
77 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
62 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
49 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
44 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
73 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
68 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
64 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: ...
0
votes
1answer
81 views

How to find positive integers where the multiplicative modular inverse is equal to itself for mod n?

This a question sparked from Project Euler Question. I really devoted so much time to search an efficient solution however no output. What are some possibles theorems or formulas that are useful in ...
4
votes
2answers
240 views

A conjecture on $\phi(n)$

Let $\phi(n)$ denote the Euler totient function of $n $. Then let $N$ be a number such that $\phi(N)$ divides $N$ . Also let $I_1= \frac{N}{\phi(N)}$ which is defined as the "Second order Index of ...
1
vote
1answer
199 views

Time complexity of Euler totient function?

To calculate $\phi(n)$, I iterate $k=1$ to $n$ and count how many times $gcd(k,n)=1$. Would the runtime of the function still be considered $O(n)$? Or would it be $O(n log n)$ due to the gcd?
3
votes
1answer
45 views

Lower and upper bounds for the length of phi-chains wanted

For calculating $$a \uparrow \uparrow n\ (mod\ m)$$ the chain $$m , \phi(m) , \phi(\phi(m)) , \phi(\phi(\phi(m))) , ... $$ is useful. As $\phi^n(m)=1$ for some n, the above modulo calculation ...