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
0answers
16 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's conjecture is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
0
votes
0answers
27 views

Euler Totient Function and new fraction numbers

Euler’s Totient Function can be used to calculate the count of new fraction numbers [below 1] as the divisor increases. New fractions identified are always either odd/odd, even/odd or odd/even. With ...
0
votes
0answers
19 views

Is this approach to Lehmer's totient problem going anywhere?

So Lehmer's totient problem states that $k\phi(n) = n-1$ and $k$ is integer and $n$ is composite. This is my first, obviously futile attempt. But what do you think of the approach to the problem? Is ...
1
vote
2answers
63 views

$2017^{2016^{2015}} \mod 1000$

I'm trying to solve the following exercise: $$2017^{2016^{2015}} \mod 1000,$$ here's what I've already come up with: Using Euler's conrgruence, one finds that $$2017^{2016^{2015}} \equiv ...
7
votes
1answer
116 views

What is $\varphi(0)$? [duplicate]

$\varphi$ is Euler's totient function. My question is: When/if $\varphi$ is defined at $0$, what is it usually defined as? Is there a "most natural" or more commonly accepted definition of ...
8
votes
2answers
185 views

Euler phi function and powers of two

For small values of n$\ge$1 it appears that one has the inequality $\phi(2^n)$ $\le$ $\phi(2^n + 1)$. However, it seems unlikely that this would hold for all n . Question: Are there any explicit ...
1
vote
2answers
50 views

$\liminf_{n\to\infty} \frac{\varphi(n)}{n} = 1$, not $0$

Let $\varphi(n) = \sharp\{1\leq x \leq n : (x,n) = 1\}$. Then $\liminf_{n\to\infty} \frac{\varphi(n)}{n} = 1$. My attempt: $\inf_{k\geq n}\frac{\varphi(k)}{k} \leq 1$ since for $n = 2$, this ...
19
votes
2answers
168 views

For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$. Let $n\ge 2$ be a positive integer. Show that there ...
1
vote
2answers
38 views

Prove that Euler phi function is multiplicative by a given theorem

I had proven a theorem which states that If $G=\langle a\rangle$ has order $rs$ , where $(r,s)=1$. Then there are unique $b,c\in G$ with $b$ of order $r$, $c$ of order $s$ and $a=bc$. There is ...
1
vote
1answer
42 views

If $\varphi(mn)=\lambda \varphi(m)\varphi(n)$ what should be written for $\lambda$

Respected All. I am studying number theory where I came to know that $\varphi(n), \sigma(n)$ both are multiplicative function ; In other words, if $(m,n)=1$ then \begin{align} ...
0
votes
0answers
35 views

Show that for no positive integer $n$ we can have $\phi(n) = n/4$ or $\phi(n) = n/5$ [duplicate]

Show that for no positive integer $n$ we can have $\phi(n) = n/4$ or $\phi(n) = n/5$. I understand why we can't have $\phi(n) = n/4$ or $\phi(n) = n/5$ however I don't know how to show this.
0
votes
5answers
88 views

Deriving Euler's theorem from Fermat's little theorem

I would like to know why $a^p \equiv a \pmod p$ is the same as $a^{p-1} \equiv 1 \pmod p$, and also how Fermat's little theorem can be used to derive Euler's theorem, or vice versa. Please keep in ...
2
votes
3answers
70 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, ...
2
votes
3answers
63 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
85 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
35 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
78 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
129 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
70 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
83 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
68 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
56 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
40 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
74 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
25 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
45 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
18 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
113 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
61 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 ...
5
votes
4answers
79 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
83 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
48 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
34 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
60 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 ...
2
votes
2answers
65 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
135 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
6answers
140 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
76 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
74 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
59 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
50 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
57 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
452 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.
2
votes
3answers
106 views

What is the Euler Totient of Zero?

Wolfram MathWorld defines the Euler Totient function as follows: ...
2
votes
3answers
112 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
84 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)$.