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
15 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
70 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
35 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
0answers
23 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
67 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
32 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
51 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
39 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 ...
0
votes
1answer
35 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
19 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
87 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
85 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
122 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
42 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
128 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
58 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
32 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
24 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
78 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
308 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
80 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
34 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
52 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
53 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
46 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
30 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
69 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
65 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
55 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
75 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
70 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
226 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
116 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
36 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 ...
1
vote
2answers
44 views

Euler's Totient Function Problem with my Understanding

Solve φ36 List of relatively prime numbers: 1,2,3,4,6,9,12,18,36 So from this I would say that φ36 = 9, but using an online calculator I got it to be 12. Where am I going wrong?
0
votes
1answer
79 views

On Euler totient function sum

Let $q$ an arbitrary integer. Is there any chance of getting a bound like $$\underset{d\mid q}{\sum}\frac{1}{\phi\left(q/d\right)^{2}}\ll\frac{1}{\phi\left(q\right)^{2}}?$$
7
votes
2answers
217 views

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?

Why is does euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it ...
2
votes
1answer
114 views

Why is Euler's totient function equal to (p-1)(q-1) when N=pq and p and q are prime? [duplicate]

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires ...
3
votes
5answers
290 views

Properties of the euler totient function

Why is it that the euler totient function has the following condition true based on its definition? $$ \phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1} $$ A proof would be awesome and an ...
0
votes
2answers
98 views

Define ≡ in this situation?

"Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$." (number $5$). I'm looking at this, and i'm not sure what the $\equiv$ means in this ...
0
votes
2answers
41 views

Prove that $\varphi(n) = n \cdot \prod\limits_{i=1}^l(p_i - 1) / p_i$

In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} \cdot \ldots \cdot p_l^{k_l}$ and $p_1, \ldots, p_l$ are all distinct prime numbers then ...
0
votes
1answer
73 views

Proof that the euler totient function is multiplicative, correctness?

I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong? Proof: We try to ...
0
votes
3answers
78 views

Euler's phi function and perfect numbers

Here is the prompt Prove that $\phi(P)=2^{k-1}(2^{k-1}-1)$, given that $P>6$ is an even perfect number. This is what i did, $P = 2^{p-1}(2^p-1)$, through Euler's theorem ...
0
votes
1answer
63 views

Suppose that n > 1. Prove that n divides $ φ (2^n - 1) $ . [duplicate]

Suppose that n > 1. Prove that n divides $ φ(2^n - 1) $ . Hint: Show that 2 has order n mod $ 2^n - 1 $
1
vote
0answers
23 views

Counting Chains of Bounded Types

You have pearl of 3 types. Type 1 pearl can be of color from 1 to X. Type 2 pearl can be of color from X+1 to X+Y Type 3 pearl can be of color from X+Y+1 to X+Y+Z. You have unlimited supply of ...
0
votes
1answer
27 views

Let $a,m\in\mathbb{N^*}$, with $m>1$, such that $(a,m)=1$. Show that, if $n_1\equiv n_2\pmod{\phi(m)}$, then $a^{n_1}\equiv a^{n_2}\pmod m$

Let $a,m\in\mathbb{N^*}$, with $m>1$, such that $(a,m)=1$. Show that, if $n_1\equiv n_2\pmod{\phi(m)}$, then $a^{n_1}\equiv a^{n_2}\pmod m$. I thought about some things, but nothing ...
1
vote
5answers
137 views

$2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$ I tried, $2730=13\cdot5\cdot7\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
1
vote
1answer
41 views

I suppose $(a,m)=(a-1,m)=1$, show that $1+a+a^2+\ldots+a^{\phi(m)-1}\equiv0\pmod m$

I suppose $(a,m)=(a-1,m)=1$, show that $$1+a+a^2+\ldots+a^{\phi(m)-1}\equiv0\pmod m$$ I tried $$1+a+a^2+a^{\phi(m)-1}=\frac{a^{\phi(m)}-1}{a-1}$$ I believe that this equality that put up help, ...
0
votes
5answers
117 views

For every positive integer n greater than $2$, $\phi(n)$ is an even integer.

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer. I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show ...