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 ...
- 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 $...
- 2,823
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 ...
- 37
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 ...
- 99
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
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
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
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 ...
- 13
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
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
0
votes
1
answer
163
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 ...
user243301
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 ...
user243301
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
0
votes
3
answers
167
views
About the solutions of $x^{\varphi(yz)}+y^{\varphi(xz)}=z^{\varphi(xy)}$, being $\varphi(n)$ the Euler's totient
In this post we denote the Euler's totient function as $\varphi(n)$ for integers $n\geq 1$. I wondered about the solutions of the equation
$$x^{\varphi(yz)}+y^{\varphi(xz)}=z^{\varphi(xy)}\tag{1}$$
...
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
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
2
votes
0
answers
55
views
On variations of Erdős squarefree conjecture: presentation and a question as a simple case
I'm inspired in the so-called Erdős squarefree conjecture, this section from Wikipedia, to state in this post a question, involving a different arithmetic function, that due its difficulty I feel as ...
user243301
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 ...
user243301
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
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
1
answer
162
views
On even integers $n\geq 2$ satisfying $\varphi(n+1)\leq\frac{\varphi(n)+\varphi(n+2)}{2}$, where $\varphi(m)$ is the Euler's totient
This afternoon I am trying to get variations of sequences inspired from the inequality that defines the so-called strong primes, see the definition of this inequality in number theory from this ...
user243301
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
2
votes
1
answer
105
views
Square-free integers in the sequence $\lambda+\prod_{k=1}^n(\varphi(k)+1)$, where $\lambda\neq 0$ is integer
While I was exploring the squares in the sequence defined for integers $n\geq 1$
$$\prod_{k=1}^n(\varphi(k)+1),\tag{1}$$
where $\varphi(m)$ denotes the Euler's totient function I wondered a different ...
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
0
votes
0
answers
708
views
If $a\mid b$ then $\phi(a)\mid \phi(b)$ for $a,b\in\mathbb{N}$ [duplicate]
Hey I would like to show that
$a\mid b\Rightarrow \varphi(a)\mid\varphi(b)\qquad a,b\in\mathbb{N}$
where $\varphi(n)$ is the the totient function.
My try:
Let $a,b\in\mathbb{N}$ and $a\mid b$. ...
- 4,794
1
vote
1
answer
823
views
How to find modulo using Euler theorem?
I don't know how that's possible using phi, the question starts with this one:
a) Decompose 870 in prime factors and compute, ϕ(870)
I know how to resolve this, first 870 = 2*3*5*29 and ϕ(870)= ...
- 31
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
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
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
1
vote
1
answer
151
views
Factorization of Euler totient function
We know that if $~n = p_{1}^{a_1} \cdots p_{s} ^ {a_s}~$ then $~\phi(n) = p_1^{a_1 - 1}(p_1 - 1)\cdots p_s^{a_s - 1} (p_s - 1)$.
If $~q~$ is prime dividing $~\phi(n)~$ then there are two situations:...
- 2,183
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
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 ...
- 55
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
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
0
votes
2
answers
57
views
Prove RSA formula to be correct
How can I mathematically prove that if:
n = pq
then
$\phi$(n) = n + 1 - (p + q)
I could prove it ofcourse with an example, but I'm sure there must be a better way.
Any help would be appreciated
- 49