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 = ...
- 11.9k
2
votes
0
answers
68
views
Largest possible prime factor for given $k$?
Let $k$ be a positive integer.
What is the largest possible prime factor of a squarefree positive integer $\ n\ $ with $\ \omega(n)=k\ $ (That is, it has exactly $\ k\ $ prime factors) satisfying the ...
- 85.1k
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 $...
- 685
0
votes
1
answer
81
views
Totient minimal value for semiprimes
I have two question concerning Euler Totient of semiprimes.
First question : given $N=p_1 * p_2$ and $M=p_3*p_4$ where $p_1,p_2,p_3,p_4$ are prime numbers greater than 5; and $M>N$ this means that ...
- 40.9k
1
vote
1
answer
396
views
Using Euler's Totient Function, how do I find all values n such that, $\varphi(𝑛)=14$
I just recently started working with Euler's Totient Function, and I came across the problem of solving for all possible integers $n$ such that $\varphi(n)=14$. I know there are similar questions with ...
- 39.9k
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
- 931
2
votes
2
answers
165
views
Use congruences to factor $n=87463$ (Fermat's Factorization?)
I'm studying for my number theory test tomorrow, and these are the last questions in my study guide. I think I understand Fermat's factorization, however, I can't tell how my professor wants us to ...
- 64.1k
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?
CommunityBot
- 1
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
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 ...
- 64.1k
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$ ...
CommunityBot
- 1
2
votes
1
answer
68
views
On miscellaneous questions about perfect numbers II
Let $\varphi(m)$ the Euler's totient function and $\sigma(m)$ the sum of divisors function. We also denote the product of primes dividing an integer $m>1$ as $\operatorname{rad}(m)$, that is the ...
- 179
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 ...
- 5,295
1
vote
1
answer
975
views
Given $\varphi (n)$ and $n$ for large values, can we know prime factors of $n$
If a number is product of two primes, then given its totient function, we can know its prime factors, but how do we do this in generic case? If the number could have more than two prime factors can ...
- 4,815