All Questions
Tagged with prime-factorization totient-function
38
questions
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
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
7
votes
1
answer
1k
views
On factoring and integer given the value of its Euler's totient function.
In an entrance test for admission into an undergraduate course in mathematics the following question was asked.
Consider the number $110179$ this number can be expressed as a product of two distinct ...
- 453
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
6
votes
0
answers
153
views
Estimation of the number of solutions for the equation $\sigma(\varphi(n))=\sigma(\operatorname{rad}(n))$
For integers $n\geq 1$ in this post we denote the square-free kernel as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p,$$ that is the product of distinct primes dividing an ...
user243301
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
5
votes
2
answers
98
views
Given $k$, what is the largest number $n$, such that $\phi(n) \le k$
Let $k$ be a positive integer and $n$ be the largest number $n$ with the property
$\phi(n) \le k$.
Does such a number $n$ exist for every $k$ ?
How can I determine the number $n$ ?
Such a number $n$ ...
- 85.1k
4
votes
1
answer
331
views
Markov triples that survive Euler's totient function
I'm inspired in a recent post of this MSE. We denote the Euler's totient function in this post as $$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Suppose we have three positive integers $a,...
user243301
4
votes
2
answers
308
views
On questions involving the radical of an integer and different number theoretic functions: the Euler's totient function
We denote for an integer $n>1$ its square-free kernel as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p,$$
with the definition $\operatorname{rad}(1)=1$. You can see this ...
user243301
3
votes
3
answers
251
views
On the equation $\varphi(n)=\left(\frac{1+\sqrt{1+8n}}{8}\right)\cdot\left(\operatorname{rad}(n)-\frac{1+\sqrt{1+8n}}{2}\right)$
An integer is said to be an even perfect number if satisifies $\sigma(n)=2n$, where $\sigma(n)$ is the sum of the positive divisors of $n$. The first few even perfect numbers are $6,28,496$ and $8128$....
user243301
3
votes
2
answers
145
views
Euler's Totient Function: $\phi(n)\geq n\cdot 2^{-r}$.
My friend's teacher made a list with this problem: If $n$ has $r$ distinct prime factors, show that:
$$\phi(n)\geq n\cdot 2^{-r}$$
I tried to help her, but I am not very good in number theory
- 65
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
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
3
votes
1
answer
236
views
Factorization of large (60-digit) number
For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$
To calculate a private exponent in the encryption ...
- 1,218
3
votes
0
answers
53
views
An integer sequence defined from a variation of the Lucas–Lehmer primality test: the case of the Euler's totient function
I did a variation of the so-called Lucas–Lehmer primality test,
I say this Wikipedia. I've used the Euler's totient function
$$\varphi(n)=n\prod_{\substack{p\mid n\\ p\text{ prime}}}\left(1-\frac{1}{...
user243301