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)

4
votes
3answers
35 views

Calculating Euler's totient function values.

I never understood how to calculate values of Euler's totient function. Can anyone help? For example, how do I calculate $\phi(2010)$? I understand there is a product formula, but it is very ...
1
vote
3answers
26 views

Euler's theorem (modular arithmetic) for non-coprime integers

I am trying to calculate $10^{130} \bmod 48$ but I need to use Euler's theorem in the process. I noticed that 48 and 10 are not coprime so I couldn't directly apply Euler's theorem. I tried breaking ...
2
votes
1answer
31 views

Proving the existence of a bijection between $U_{mn}$ and $U_m \times U_n$ where $(m,n)=1$ , there by proving Euler $\phi$ is multiplicative

Without proving before hand that Euler's phi $(\phi)$ function is multiplicative , can we prove that there is a bijection between $U_{mn}$ and $U_m \times U_n$ , for any pair of relatively prime ...
1
vote
2answers
51 views

Finding a power of x to be equivalent to some number in modular arithmetic

I'm struggling to work through how to find $x$ such that $x^{11}\equiv 10\mod42$. It has been previously worked out that $11^{-1}\equiv 15\mod41$, although I'm unsure how this helps. What I've so ...
0
votes
3answers
28 views

What is the product of $p_i-1 \over p_i$ [duplicate]

I am trying to find the value of $\prod_{i=0}^{\infty}{p_i-1 \over p_i}$ = ${\lim_{x \to \infty}} {\phi(p_x!) \over p_x!}$ Where $p_x!$ is the $x$th primorial, and $p_i$ is the $i$th prime number. I ...
2
votes
2answers
52 views

Proof involving Euler totient function and modular arithmetic

Let $ n = pq$ where $p$ and $q$ are distinct primes, and let $e$ be an integer coprime to $ \varphi (n)$. Explain why there is an integer $d$ such that $ed = 1 $ (mod $ \varphi(n)$). Prove that ...
3
votes
1answer
52 views

Efficiently doing prime factorisation by hand

I have a yes/no question first (if 2 questions are allowed in 1 post). When doing prime factorisation for using the Euler totient function can you use a particular prime more than once. (i.e. $p_{1} ...
0
votes
2answers
39 views

Solve the system of modular equations

I have the system $$2^a \equiv 7 \mod 27 \\2^{18} \equiv 1 \mod 27$$ How can I solve this system? I was thinking of using Chinese remainder theorem but 27 and 27 are not coprime.
1
vote
2answers
55 views

Extending Euler's Theorem gives minus 1 - why?

Euler's Theorem states that for some coprimes $n$ and $a$: $a^{\phi(n)} \equiv 1 \mod n$ Example: $ a = 10, p=7, q=11, n=p*q=77, \phi(n) =(p-1)*(q-1)= 60$ $10^{60} \equiv 1 \mod 77$ When I take ...
1
vote
1answer
38 views

Lehmer's conjecture/Lehmer's totient problem

I came across Lehmers problem in Wikipedia and do not grasp why it may be of any interest. Are there any serious consequences or insights if it is really confirmed ? I suppose people who struggle(d) ...
1
vote
2answers
66 views

Euler's totient function for large numbers

I know that $\phi(n)$, Euler's totient function, defines the number of all integers less than or equal to $n$ that are relatively prime to $n$. I know that there is a trick to finding this with the ...
2
votes
1answer
72 views

Two conjectures regarding $\varphi(n)$

There is a famous unsolved problem called Lehmer's Totient Problem which states that, $\varphi(n)\mid n-1 \implies n$ is a prime. Where $\varphi(n)$ is Euler's Totient Function. I was ...
0
votes
0answers
61 views

Approach name - Ross Millikan's answer

I want to know the name of an approach (formula) in the first comment of this question (@Ross Millikan's answer) Counting arrays with gcd 1 Thanks
5
votes
1answer
64 views

Lower bound of Euler phi function times sum of divisors

After some work, I got this nice inequality: $$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$ where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm ...
0
votes
2answers
40 views

Group theoretical proof of $\varphi(rs)=\varphi(r)\varphi(s)$ through generators of the group.

Given a group $G=\langle a\rangle$ of order $rs$, with $(r,s)=1$, I showed there exist unique $b,c\in G$ such that $a=bc$ with $b$ of order $r$ and $c$ of order $s$. The latter is a direct consecuense ...
0
votes
3answers
478 views

Counting arrays with gcd 1

I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1. Constraints: $1 \leq A_i \leq M$ and $A_i$ ...
1
vote
1answer
63 views

Number of coprimes of $n$ divisible by 3

I'm looking for a formula for $C(n)$ := the number of coprimes of $n$ in the range $[1, n]$ divisible by 3, where $n$ is any positive integer. The formula should be quick to compute, preferably at ...
2
votes
1answer
73 views

Proof of Euler's Totient Theorem

I have seen quite a few proofs of Euler's Totient Theorem that $a^{\phi(n)}≡1 \pmod n$ for all $a$ relatively prime to $n$. However, none have been done using induction. That is what I have been ...
8
votes
3answers
368 views

Very elementary proof of that Euler's totient function is multiplicative

Well, I know two or three proofs of this fact $$\gcd(m,n)=1\implies \varphi(mn)=\varphi(m)\varphi(n)$$ where $\varphi$ is the totient function. My problem is this: I'd like to explain this to some ...
0
votes
1answer
40 views

General Behavior of Euler Totient Function

If we have two integer M and N such that $$GCD(M,N) = k$$ Then what is $$\phi(MN)$$ There is a famous identity which states: $$GCD(M,N)= 1 \rightarrow \phi (MN) = \phi(M)\phi(N)$$ And now I am ...
3
votes
3answers
103 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 ...
4
votes
1answer
63 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
56 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
24 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$
2
votes
0answers
64 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
0
votes
1answer
45 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
47 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
58 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
92 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
95 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
1
vote
0answers
48 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
90 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
70 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
61 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
44 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
45 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
47 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 ...
2
votes
1answer
68 views

How to calculate “gcd product” $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$

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
61 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
545 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
22 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.
7
votes
2answers
195 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
75 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
29 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
174 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
135 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
51 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
54 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
13 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
93 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 ...