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)

2
votes
3answers
62 views

Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$

Here is a very elementary number theory proof using strong induction. Please mark/grade. Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler's phi function, $n,d\in\mathbb{N}$ First, ...
1
vote
2answers
45 views

Application of Euler's theorem apart from finding last digits of huge numbers

I am looking for clever applications of Euler's Theorem. On browsing the internet, I see that nearly all the applications of the theorem asks for finding last few digits of a huge number. The only ...
7
votes
1answer
81 views

Is the set $\phi(\mathbb{N})$ syndetic?

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded. Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function) I've thought quite a ...
3
votes
2answers
33 views

Is the relationship between these two sequences, identical but for signs, trivial?

Sums of divisors of product of first $n$ primes has same sequence as products of totients of first $n$ primes, but with alternating signs. OEIS A005867 Mathematica code shown: Table[Sum[ ...
4
votes
1answer
75 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
7
votes
0answers
127 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
2
votes
1answer
60 views

The equation $\phi (x)=n$ has only a finite number of solutions.

While reading about Euler's totient function, I came across this question: Prove that for a fixed $n$, the equation $\phi (x)=n$ has only a finite number of solutions. I have thought a lot about ...
2
votes
3answers
82 views

Sum of super exponentiation

$f(x,n)=x^{2^{1}}+x^{2^{2}}+x^{2^{3}}+...+x^{2^{n}}$ Example: $f(2,10)$ mod $1000000007$ = $180974681$ Calculate $\sum_{x=2}^{10^{7}} f(x,10^{18})$ mod $1000000007$. We know that $a^{b^{c}}$ mod ...
2
votes
2answers
78 views

Proof to a property of Euler's totient function

The property is $$\sum_{d|n}\phi(d) = n$$ And the proof provided is If $d$ divides $n$, let $C_d$ be the unique subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d$, and let $\Phi_d$ be the set of ...
2
votes
4answers
65 views

Understanding Primitive roots

I am trying to find a single primitive root modulo $11$. The definition in my textbook says "Let $a$ and $n$ be relatively prime integers with ($a \neq 0$) and $n$ positive. Then the least ...
0
votes
2answers
54 views

Determining whether there exists an integer $a$ such that $\text{ord}_{20}(a) = 8$.

I am trying to determine whether there exists an integer $a$ such that $\text{ord}_{20}(a) = 8$. I know that if $(a,n) = 1$ and $n>0$, then $\text{ord}_{n}(a)\mid \phi(n)$. I cannot use any ...
0
votes
4answers
39 views

Determining whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$.

I am trying to determine whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$, where $\text{ord}_{17}(a)$ is the least integer $k$ such that $a^k \equiv 1\pmod{\! 17}$. This is equivalent to ...
3
votes
1answer
65 views

Is there $\phi(n)=n/6$

I know how to find for which $n$ $\phi(n)=n/2$ or $\phi(n)=n/3$, my method for finding those was simply to find primes $p$ that satisfy $\Pi_p$$_|$$_n$$1-1/p$ $ = 1/2$ or $1/3$. However, I don't ...
0
votes
0answers
23 views

Show that $\sum_{d \mid p-1} T(d) = p-1$ where $p$ is prime and $T(d) = \# \{a \mid 1 \le a \le p - 1, \, (a,\,p-1)=d \}$.

I'm trying to show that $$\sum_{d \mid p-1} T(d) = p-1,$$ where $p$ is prime and $T(d) = \# \{a \mid 1 \le a \le p - 1, \, (a,\,p-1)=d \}$. I really don't even know how to begin on this problem. A ...
1
vote
2answers
22 views

Find remainder using euler function?

How to find the remainder of $\frac{208^{181}}{209}$ using Euler's function or Fermat's theorem? (I solved this kind of problem easily when base, $208$, is smaller than the power, $184$, but it's hard ...
0
votes
1answer
44 views

prove that for each $n \in\mathbb N$ odd, $\phi(n) \ne 2^{32}$

I need to prove that for each $n \in\mathbb N$ odd, $$\phi(n) \ne 2^{32}.$$ What I tried: I assumed that $\phi(n)$ is indeed a power of 2 then, because of this assumption I know that $ n = p_1 ...
1
vote
2answers
53 views

Show that $10^{n(p-1)}\equiv 1\pmod{\! 9p}$ for $p\ge 7$

I need to prove that for each prime $p \ge 7$ and for each $n \in\Bbb N$ $$10^{n(p-1)} \equiv 1 \pmod {9p}$$ What I've tried: I know $10$ is coprime to $9$ and $p$, so it is coprime to $9p$. I ...
0
votes
1answer
17 views

Show that $(M^{e})^d \equiv M$ (mod n).

I need to show the following. Given $n,e \in \mathbb{Z^+}$ such that $gcd(e,\phi(n)) =1$, let $d$ be an inverse of $e$ (mod $\phi(n)$), and let $M \in \mathbb{Z}$ such that gcd($M,n$) = 1. Show that ...
0
votes
5answers
105 views

Find $7^{999,999}$ modulo (10)

I am trying to find $7^{999,999}$ modulo (10) using Euler's Theorem: If $m \in \mathbb{Z^+}, a \in \mathbb{Z}, (a,m) = 1$ then $a^{\phi(m)} \equiv 1$ (mod m). I am unsure though how to use it ...
2
votes
3answers
58 views

For $n > 2, n \in \mathbb{Z}$, show the sum of integers coprime to $n$ in the range $[1,n-1]$ is equal to $\frac{1}{2}n \phi(n)$

For $n > 2, n \in \mathbb{Z}$, show the sum of integers coprime to $n$ in the range $[1,n-1]$ is equal to $\frac{1}{2}n \phi(n)$ Firstly $\phi(n)$ is Euler's totient function, the number of ...
4
votes
4answers
71 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
82 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
47 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
33 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
53 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
60 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 ...
4
votes
1answer
127 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: ...
3
votes
5answers
119 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
74 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
68 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
57 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
49 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
55 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 ...
15
votes
2answers
422 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
31 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
70 views

What is the Euler Totient of Zero?

Wolfram MathWorld defines the Euler Totient function as follows: ...
2
votes
3answers
108 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
83 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
120 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
123 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
60 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
207 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
144 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
114 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
65 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
48 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
81 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
40 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
51 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?