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
4answers
61 views

Proving that $\varphi(n)=n\prod (1-1/p)$ without using multiplicativity

$$\varphi(n)=n\prod_{p \ \text{prime}} (1-1/p)$$ Can this useful formula be derived without using the fact that Euler's totient function is multiplicative?
3
votes
2answers
71 views

Prove or disprove that $a^{\phi(n) + k} \equiv a^{k} \mod{n}$

Prove or disprove that $$ a^{\phi(n) + k} \equiv a^{k} \mod{n} $$ where $\phi(n)$ is Euler's totient function, for all positive integers $a$ and $n$, as long as $k$ is $\geq$ the ...
3
votes
2answers
42 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...
1
vote
1answer
25 views

Number theoretic function related to totient

I'm doing an excercise in Alan Baker's book A Concise Introduction to the Theory of Numbers, and I'm confused about the method spelled out for one question. I'll quote it here: Let $a$ run through ...
2
votes
1answer
27 views

Is there a standard term for this generalization of the Euler totient function?

Let $\phi_k(n)$ be the number of integers $m$ in $1\le m\le n$ for which $\gcd(m,n) = k$. Then $\phi_1(n) =\varphi(n)$, the standard totient function. This function arises in the analysis of the ...
1
vote
2answers
58 views

Show that $\sum_{n \le x} \phi (n)=\frac{x^2}{2\zeta(2)}+ O(x \log x)$

How do I show that $\sum_{n \le x} \phi (n)=\frac{x^2}{2\zeta(2)}+ O(x \log x)$, where $O$ denotes the big-$O$ notation. And we already know that $\phi (n) = \sum_{d|n} \mu (d) \frac{n}{d}$. I ...
2
votes
0answers
60 views

Euler's totient and divisors count function relationship when $[(\frac{\varphi(n)}{2}+1)\cdot(\frac{\tau(n)}{2}+1)] = n$

I am studying the Euler's totient function $\varphi(n)$ and the divisors count function, $\tau(n)$, also named $d(n)$, and recently opened a question (link here) about the following condition: ...
2
votes
5answers
79 views

When is $\phi(n)=n$ true?

For what values of n is $\phi(n)=n$ true? Just looking at tables of values it seems that $\phi(n)=n$ is true only for $n=0,1$ but I cannot come up with how to prove this. I realize that the value of ...
5
votes
2answers
73 views

Help to prove that $ U_{p} $ is a cyclic group.

As part of my study of Abstract Algebra, I’m trying to prove that $ U_{p} $ is cyclic for $ p $ a prime number. It’s a classical result, but I’m trying to prove it following four steps stated as ...
1
vote
3answers
62 views

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$ Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies ...
2
votes
4answers
51 views

Elementary theory of numbers and the phi function. [closed]

Question: Let $n$ be a natural number, and suppose that $2 \phi(n) = n$. Prove that $n$ is a power of $2$.
1
vote
2answers
46 views

Euler Phi of a number

I saw an AIME problem where you took $\phi(1000)$ and then divided by $2$. The problem is here: http://www.artofproblemsolving.com/community/u244443h580665p4722095 $\phi(1000)$ gives you how many ...
1
vote
1answer
45 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 ...
13
votes
2answers
343 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
29 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
63 views

What is the Euler Totient of Zero?

Wolfram MathWorld defines the Euler Totient function as follows: ...
2
votes
3answers
94 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 ...
5
votes
1answer
73 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
111 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
102 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
58 views

Sublists Conjecture

The conjecture: For those $k$ that have a saturated sublist $a_{j}$, the first occurrence is: $$j \geq k+3.$$ A proof will imply Oppermann and will be a start to a pattern-based attack on the ...
8
votes
3answers
191 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
139 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
110 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
53 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
55 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
42 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
67 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
37 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
46 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
77 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
55 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 ...
2
votes
1answer
35 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
83 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
134 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
23 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
108 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
59 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
53 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
53 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
38 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
67 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
60 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
54 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
59 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
54 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
88 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 ...
4
votes
1answer
90 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
65 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
6
votes
1answer
82 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 ...