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
1answer
27 views

Euler's Totient function $\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\ $,$\ $then $(n-\phi(n)) \in \Bbb P$

Recently I opened a question about what it might be a new property of Euler's Totient function. I am still studying the Totient function and I found another interesting relationship, it is very ...
7
votes
0answers
93 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
0
votes
1answer
25 views

Is sum of all divisors each multiplied by it's respective totient for a particular number is multiplicative when two numbers are coprime?

Is the formula for nth term of sequence http://oeis.org/A057660 is multiplicative when the numbers are coprime ? If yes how to prove it? And what is the answer when they are not coprime.
0
votes
3answers
51 views

What is the Euler Totient of Zero?

Wolfram MathWorld defines the Euler Totient function as follows: ...
2
votes
3answers
78 views

Number Theory : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$

I was working my way through some basic Number Theory Problems , when I came across : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$ , where $\phi(x)$ is the euler phi function I am ...
4
votes
1answer
51 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
6
votes
1answer
100 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...
3
votes
0answers
88 views

To prove $\phi(mn)\phi(d)=\phi(m)\phi(n)d$ without explicitly computing the phi function values

If $m,n$ are positive integers with g.c.d.$(m,n)=d$ , then we can show by explicitly computing respective totients that $\phi(mn)\phi(d)=\phi(m)\phi(n)d$, I want to know, is there any more elegant way ...
1
vote
0answers
38 views

Sublists Conjecture

The conjecture: For those $k$ that have a saturated sublist $a_{j}$, $j \geq k+3$. Construct a list for an arbitrary $k\geq12$: $$A=\left\lbrace \text{lpf}(n,k):1\leq ...
8
votes
3answers
163 views

Does the totient function reach all its values when restricted to odd numbers?

This question might be a duplicate, if so, I apologise in advance. It is simple, but answering it is probably harder :) Is it true, that the $\phi(n)$ function(Euler's totient function) takes on all ...
0
votes
0answers
114 views

Some feedback on the sequence $ a_n=a_{n-1}+4\phi_n $

This sequence is present at OEIS A171503. There, Jacob Siehler explains how this sequence correspond to the number of matrices with determinant one and how this number grows as we allow to vary in ...
2
votes
2answers
96 views

Find all $n$ such that $\varphi(n)=20$

How can I find all integers such that $\varphi(n)=20$, where $\varphi$ is the Euler-totient function I've seen somewhere that $\varphi(n)\ge\sqrt{n}$, for all $n$ except $n=2$ and $n=6$, without ...
0
votes
2answers
52 views

Euler's Totient Function and Cryptography Question

I'm working on a problem set for a class on intro computing and cryptography. I'm being asked to find the $n = pq$, where $p,q$ are integers (not necessarily prime), such that $\phi(n)=$ ...
1
vote
1answer
52 views

Why is $I^1=\varphi*I^0$?

Why is $I^1=\varphi*I^0$ ? where, $I^j(n)=n^j$ and $(f*g)(n)=\sum\limits_{d\in\mathbb N, d\mid n}f(d)g(\frac{n}d)$ $\varphi$ is the Euler-totient function, ...
1
vote
2answers
36 views

Number theory question about Euler's totient function

We have two natural numbers, m and n, and m divides n. Prove, that φ(m) divides φ(n) too for every m and n. φ(a) means the Euler's totient function: for an a positive integers, it is the number of ...
2
votes
2answers
56 views

Connection between GCD and totient function

I found the following formula which connects Euler's totient function with gcd at wikipedia. $$ \gcd(a,b) = \sum_{k|a \; \hbox{and} \; k|b} \varphi(k). $$ The problem is that I can not figure out ...
0
votes
1answer
36 views

Euler's totient function

Find all n such that $\varphi(n) = n/24$ This is my attempt: $24 = 2^3*3$ $\varphi(24^k) = (2^{3k}-2^{3k-1})(3^k-3^{k-1})=2^{3k}(1-1/2)*3^k(1-1/3)=2^{3k}*3^{k-1}$ $24^k/24 = 24^{k-1}= ...
2
votes
1answer
39 views

Euler's Totient function bound

Do there exist any integers $n$ such that Euler's totient function $\phi(n) < n/5$? How should I approach solving this problem?
5
votes
1answer
65 views

Connection between Euler's totient function and Fibonacci numbers

For a sequence $(a_n)$ of natural numbers define $\alpha(n):=\min\{m\in\mathbb{N}:n|a_m\}$ whenever it exists. Thus $\alpha(n)$ is the first index $m$ such that $n$ divides $a_m$. Now define the ...
2
votes
1answer
52 views

prove that there are infinitely many k such that $\phi(n) = k$ has precisely two solutions

I am asked to prove that there are infinitely many $k$ such that $\phi(n) = k$ has precisely two solutions. I think for any prime number $p \mid n$, we have $(p-1) \mid \phi(n)$. But I am not sure ...
1
vote
1answer
32 views

Proof there is no lower bound for the totient function.

I wish to show there is no constant $c$ such that $ c n \leq \varphi (n) $, is this proof correct?. From Euler's identity for the zeta function we have: $$ \prod \left( 1 - \frac{1}{p} \right) = ...
5
votes
1answer
76 views

Find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$

I need to find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$ where $ϕ(n)$ denotes Euler's totient function. What I am given: (1) You may take $ϕ(n) = 2592$. (2) $ϕ(2n) = ϕ(n)$ ...
3
votes
1answer
122 views

Euler's function $\phi$: Values such that $\phi(n)=8$, $\phi(n)=14$

Let $\phi(n) $ be Euler's Totient Function Let us consider $$ |\{ n \in \mathbb{N} : \phi (n) = 8 \} | = 5, $$ and $$ |\{ n \in \mathbb{N} : \phi (n) = 14 \} | = 0. $$ How would I go about ...
0
votes
1answer
22 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
6
votes
4answers
89 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
52 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
48 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
52 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
36 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
65 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
59 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
48 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
58 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
48 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
77 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 ...
3
votes
1answer
83 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
63 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
71 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
48 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
512 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
71 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
96 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 ...
9
votes
3answers
433 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
54 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 ...
7
votes
4answers
90 views

For what integers $n$ does $\phi(2n)=\phi(3n)$?

For what integers $n$ does $\phi(2n)=\phi(3n)$? I know that $\phi(n) = \phi(P_1^{a1})\cdots\phi(P_k^{ak}) = (P_1^{a1}-P_1^{a1-1})\cdots(P_k^{ak}-P_k^{ak-1})$ but I'm not really sure how to apply it ...
3
votes
3answers
125 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
66 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
69 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
31 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
72 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 ...