All Questions
13
questions
5
votes
1
answer
161
views
Infinitely many primes with $2$ and $3$ generating the same set of residues
Prove that there are sets $S$ and $T$ of infinitely many primes such that:
For every $p\in S$ there exists a positive integer $n$ such that $p\mid 2^{n} - 3$.
For every $p \in T$ the remainders mod $...
- 2,823
0
votes
3
answers
344
views
Euler's product formula in number theory
Is there intuitive proof of Euler's product formula in number theory (not searching for probabilistic proof) which is used to compute Euler's totient function?
- 1,276
1
vote
0
answers
801
views
number of coprimes to a less than b
We know that number of coprimes less than a number can be found using euler function https://brilliant.org/wiki/eulers-totient-function/ But if there are two numbers p,q and we need to find number of ...
- 139
7
votes
1
answer
117
views
On numbers with small $\varphi(n)/n$
Let $\Phi(n) = \varphi(n)/n = \prod_{p|n}(p-1)/p$ be the "normalized totient" of $n$.
Some facts:
$\Phi(p) = (p-1)/p < 1$ for prime numbers with $\lim_{p\rightarrow \infty}\Phi(p) = 1$
$\Phi(n) = ...
- 18.2k
8
votes
0
answers
182
views
Odd numbers with $\varphi(n)/n < 1/2$
The topic was also discussed in this MathOverflow question.
From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
- 18.2k
11
votes
7
answers
3k
views
Only finitely many $n$ such that $\phi(n) = m$
Let $\phi(n)$ be Euler's totient function.
How do I show that there are only finitely many such $n$ with $\phi(n) = m$, for each positive integer $m$?
I've written $n$ as a product of primes; $n = ...
- 2,482
2
votes
2
answers
152
views
The arithmetic function $\frac{\operatorname{rad}(2n)}{n+\varphi(n)+1}$ and a characterization of twin primes
We denote the Euler's totient function as $\varphi(n)$, and the radical of the integer $n> 1$ as
$$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p,$$
taking $\operatorname{rad}(1)...
user243301
2
votes
3
answers
650
views
For which natural numbers are $\phi(n)=2$?
I found this exercise in Beachy and Blair: Abstract algebra:
Find all natural numbers $n$ such that $\varphi(n)=2$, where $\varphi(n)$ means the totient function.
My try:
$\varphi(n)=2$ if $n=3,4,...
- 4,794
3
votes
1
answer
64
views
About the divisors of totient numbers
Are there infinitely many integers that do not divide any totient number?
My try:
If $a|b$ then $\phi(a)|\phi(b)$, so the main question would be equivalent to asking wether there are infinitely many ...
- 1,919
0
votes
1
answer
827
views
Euler's totient function and prime factorization
I want to prove the following:
Let $n \in \mathbb{N}$. Then, if
$$2\varphi(n) + 2 = n$$
holds, there exists an odd prime $p$ such that $n=2p$.
My guess is that one can use the multiplicative ...
- 337
0
votes
1
answer
85
views
Calculate Euler inverse function
Given $n$ find all values n such that: $\phi(n) = 26$.
I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point.
I'll be ...
- 489
3
votes
0
answers
68
views
Product of the Euler phi function [duplicate]
Prove the following statement: If $n, m\in\mathbb{Z} $ and $g=$gcd$(n, m) $ then is
$$\varphi(m, n) =\frac{ \varphi(m) \varphi(n) g} {\varphi(g)}. $$
Hint: Prove the statement with induction above ...
- 853
3
votes
1
answer
248
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} ...
- 1,727