All Questions
Tagged with prime-factorization totient-function
38
questions
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 ...
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 $...
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 ...
1
vote
1
answer
395
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 ...
0
votes
3
answers
343
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
vote
0
answers
794
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 ...
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 ...
7
votes
1
answer
116
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) = ...
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$ ...
1
vote
1
answer
973
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 ...
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$....
6
votes
0
answers
152
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 ...
0
votes
1
answer
162
views
On prime-perfect numbers and the equation $\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(\sigma(n))}$
While I was exploring equations involving multiple compositions of number theoretic functions that satisfy the sequence of even perfect numbers, I wondered next question (below in the Appendix I add a ...
0
votes
1
answer
195
views
Finishing the task to find the solutions of $\frac{1}{x}-\frac{1}{y}=\frac{1}{\varphi(xy)},$ where $\varphi(n)$ denotes the Euler's totient function
In this post I evoke a variant of the equations showed in section D28 A reciprocal diophantine equation from [1], using particular values of the Euler's totient function $\varphi(n)$. I ask it from a ...
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 = ...