Find solutions to $varphileft(nright)=2^32$

Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
I'm looking for some solutions to $varphileft(nright)=2^32$ where $varphi$ is the Euler's totient function.
I know that if $n=p_1^r_1cdotldotscdot p_k^r_k$ satisfies
$varphileft(nright)=2^32$ then
beginalign*
& 2^32=varphileft(nright)=prod_i=1^kp^r_ileft(1-frac1p_iright)=nprod_i=1^kleft(1-frac1p_iright)\
Rightarrowquad & n=frac2^32prodleft(p_i-1right)prod p_i
endalign*
So I was looking to compute solutions by finiding primes $p_i$
such that $p_i-1mid2^32$ and plug them into the last equation.
Those are $p_i-1inleft 2^lmid1leq lleq32right $ and
for example $p_i-1=2$ is good because then $p_i=3$ is a prime.
Plugging it into the equation gives
$$
n=frac2^32left(3-1right)cdot3=3cdot2^31
$$
But then $varphileft(3cdot2^31right)=varphileft(3right)varphileft(2^31right)=2left(2^31-2^30right)=2^31boldsymbolneq2^32$
What am I missing here?
elementary-number-theory prime-numbers totient-function
 |Â
show 1 more comment
up vote
5
down vote
favorite
I'm looking for some solutions to $varphileft(nright)=2^32$ where $varphi$ is the Euler's totient function.
I know that if $n=p_1^r_1cdotldotscdot p_k^r_k$ satisfies
$varphileft(nright)=2^32$ then
beginalign*
& 2^32=varphileft(nright)=prod_i=1^kp^r_ileft(1-frac1p_iright)=nprod_i=1^kleft(1-frac1p_iright)\
Rightarrowquad & n=frac2^32prodleft(p_i-1right)prod p_i
endalign*
So I was looking to compute solutions by finiding primes $p_i$
such that $p_i-1mid2^32$ and plug them into the last equation.
Those are $p_i-1inleft 2^lmid1leq lleq32right $ and
for example $p_i-1=2$ is good because then $p_i=3$ is a prime.
Plugging it into the equation gives
$$
n=frac2^32left(3-1right)cdot3=3cdot2^31
$$
But then $varphileft(3cdot2^31right)=varphileft(3right)varphileft(2^31right)=2left(2^31-2^30right)=2^31boldsymbolneq2^32$
What am I missing here?
elementary-number-theory prime-numbers totient-function
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
@rtybase What about it?
â Jon
Jul 13 at 8:09
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26
 |Â
show 1 more comment
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I'm looking for some solutions to $varphileft(nright)=2^32$ where $varphi$ is the Euler's totient function.
I know that if $n=p_1^r_1cdotldotscdot p_k^r_k$ satisfies
$varphileft(nright)=2^32$ then
beginalign*
& 2^32=varphileft(nright)=prod_i=1^kp^r_ileft(1-frac1p_iright)=nprod_i=1^kleft(1-frac1p_iright)\
Rightarrowquad & n=frac2^32prodleft(p_i-1right)prod p_i
endalign*
So I was looking to compute solutions by finiding primes $p_i$
such that $p_i-1mid2^32$ and plug them into the last equation.
Those are $p_i-1inleft 2^lmid1leq lleq32right $ and
for example $p_i-1=2$ is good because then $p_i=3$ is a prime.
Plugging it into the equation gives
$$
n=frac2^32left(3-1right)cdot3=3cdot2^31
$$
But then $varphileft(3cdot2^31right)=varphileft(3right)varphileft(2^31right)=2left(2^31-2^30right)=2^31boldsymbolneq2^32$
What am I missing here?
elementary-number-theory prime-numbers totient-function
I'm looking for some solutions to $varphileft(nright)=2^32$ where $varphi$ is the Euler's totient function.
I know that if $n=p_1^r_1cdotldotscdot p_k^r_k$ satisfies
$varphileft(nright)=2^32$ then
beginalign*
& 2^32=varphileft(nright)=prod_i=1^kp^r_ileft(1-frac1p_iright)=nprod_i=1^kleft(1-frac1p_iright)\
Rightarrowquad & n=frac2^32prodleft(p_i-1right)prod p_i
endalign*
So I was looking to compute solutions by finiding primes $p_i$
such that $p_i-1mid2^32$ and plug them into the last equation.
Those are $p_i-1inleft 2^lmid1leq lleq32right $ and
for example $p_i-1=2$ is good because then $p_i=3$ is a prime.
Plugging it into the equation gives
$$
n=frac2^32left(3-1right)cdot3=3cdot2^31
$$
But then $varphileft(3cdot2^31right)=varphileft(3right)varphileft(2^31right)=2left(2^31-2^30right)=2^31boldsymbolneq2^32$
What am I missing here?
elementary-number-theory prime-numbers totient-function
asked Jul 13 at 7:56
Jon
500413
500413
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
@rtybase What about it?
â Jon
Jul 13 at 8:09
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26
 |Â
show 1 more comment
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
@rtybase What about it?
â Jon
Jul 13 at 8:09
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
@rtybase What about it?
â Jon
Jul 13 at 8:09
@rtybase What about it?
â Jon
Jul 13 at 8:09
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.
Incidentally, $3ÃÂ2^32$ is not the minimal solution. The number $5ÃÂ2^31$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
add a comment |Â
up vote
2
down vote
Another way to look at the totient function is
$$varphi(n)=p_1^r_1-1(p_1-1)cdot p_2^r_2-1(p_2-1)...p_k^r_k-1(p_k-1)=2^32$$
Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=overline2..k$ and $p_i=2^m_i+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i mid 2^32$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!)
$$varphi(2^33)=2^32$$
$$varphi(3cdot2^32)=varphi(3)cdotvarphi(2^32)=2^32$$
$$varphi(17cdot2^29)=varphi(17)cdotvarphi(2^29)=2^32$$
$$varphi(3cdot17cdot2^28)=varphi(3)cdotvarphi(17)cdotvarphi(2^28)=2^32$$
$$varphi(3cdot5cdot17cdot2^26)=varphi(3)cdotvarphi(5)cdotvarphi(17)cdotvarphi(2^26)=2^32$$
and so on ... There are $5$ Fermat primes less than $2^32$: $left 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1right$. You will have to look at all the combinations $binom50+binom51+...+binom55=2^5$ and complement with some $varphi(2^n)=2^n-1$ to obtain $2^32$.
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.
Incidentally, $3ÃÂ2^32$ is not the minimal solution. The number $5ÃÂ2^31$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
add a comment |Â
up vote
1
down vote
accepted
In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.
Incidentally, $3ÃÂ2^32$ is not the minimal solution. The number $5ÃÂ2^31$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.
Incidentally, $3ÃÂ2^32$ is not the minimal solution. The number $5ÃÂ2^31$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?
In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.
Incidentally, $3ÃÂ2^32$ is not the minimal solution. The number $5ÃÂ2^31$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?
answered Jul 13 at 9:59
Oscar Lanzi
10k11632
10k11632
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
add a comment |Â
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
1
1
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $fracvarphileft(nright)prodleft(p_i-1right)$ to be one of the $p_i$'s?
â Jon
Jul 13 at 10:22
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
Yes, that's how it works.
â Oscar Lanzi
Jul 13 at 11:46
add a comment |Â
up vote
2
down vote
Another way to look at the totient function is
$$varphi(n)=p_1^r_1-1(p_1-1)cdot p_2^r_2-1(p_2-1)...p_k^r_k-1(p_k-1)=2^32$$
Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=overline2..k$ and $p_i=2^m_i+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i mid 2^32$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!)
$$varphi(2^33)=2^32$$
$$varphi(3cdot2^32)=varphi(3)cdotvarphi(2^32)=2^32$$
$$varphi(17cdot2^29)=varphi(17)cdotvarphi(2^29)=2^32$$
$$varphi(3cdot17cdot2^28)=varphi(3)cdotvarphi(17)cdotvarphi(2^28)=2^32$$
$$varphi(3cdot5cdot17cdot2^26)=varphi(3)cdotvarphi(5)cdotvarphi(17)cdotvarphi(2^26)=2^32$$
and so on ... There are $5$ Fermat primes less than $2^32$: $left 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1right$. You will have to look at all the combinations $binom50+binom51+...+binom55=2^5$ and complement with some $varphi(2^n)=2^n-1$ to obtain $2^32$.
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
add a comment |Â
up vote
2
down vote
Another way to look at the totient function is
$$varphi(n)=p_1^r_1-1(p_1-1)cdot p_2^r_2-1(p_2-1)...p_k^r_k-1(p_k-1)=2^32$$
Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=overline2..k$ and $p_i=2^m_i+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i mid 2^32$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!)
$$varphi(2^33)=2^32$$
$$varphi(3cdot2^32)=varphi(3)cdotvarphi(2^32)=2^32$$
$$varphi(17cdot2^29)=varphi(17)cdotvarphi(2^29)=2^32$$
$$varphi(3cdot17cdot2^28)=varphi(3)cdotvarphi(17)cdotvarphi(2^28)=2^32$$
$$varphi(3cdot5cdot17cdot2^26)=varphi(3)cdotvarphi(5)cdotvarphi(17)cdotvarphi(2^26)=2^32$$
and so on ... There are $5$ Fermat primes less than $2^32$: $left 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1right$. You will have to look at all the combinations $binom50+binom51+...+binom55=2^5$ and complement with some $varphi(2^n)=2^n-1$ to obtain $2^32$.
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Another way to look at the totient function is
$$varphi(n)=p_1^r_1-1(p_1-1)cdot p_2^r_2-1(p_2-1)...p_k^r_k-1(p_k-1)=2^32$$
Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=overline2..k$ and $p_i=2^m_i+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i mid 2^32$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!)
$$varphi(2^33)=2^32$$
$$varphi(3cdot2^32)=varphi(3)cdotvarphi(2^32)=2^32$$
$$varphi(17cdot2^29)=varphi(17)cdotvarphi(2^29)=2^32$$
$$varphi(3cdot17cdot2^28)=varphi(3)cdotvarphi(17)cdotvarphi(2^28)=2^32$$
$$varphi(3cdot5cdot17cdot2^26)=varphi(3)cdotvarphi(5)cdotvarphi(17)cdotvarphi(2^26)=2^32$$
and so on ... There are $5$ Fermat primes less than $2^32$: $left 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1right$. You will have to look at all the combinations $binom50+binom51+...+binom55=2^5$ and complement with some $varphi(2^n)=2^n-1$ to obtain $2^32$.
Another way to look at the totient function is
$$varphi(n)=p_1^r_1-1(p_1-1)cdot p_2^r_2-1(p_2-1)...p_k^r_k-1(p_k-1)=2^32$$
Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=overline2..k$ and $p_i=2^m_i+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i mid 2^32$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!)
$$varphi(2^33)=2^32$$
$$varphi(3cdot2^32)=varphi(3)cdotvarphi(2^32)=2^32$$
$$varphi(17cdot2^29)=varphi(17)cdotvarphi(2^29)=2^32$$
$$varphi(3cdot17cdot2^28)=varphi(3)cdotvarphi(17)cdotvarphi(2^28)=2^32$$
$$varphi(3cdot5cdot17cdot2^26)=varphi(3)cdotvarphi(5)cdotvarphi(17)cdotvarphi(2^26)=2^32$$
and so on ... There are $5$ Fermat primes less than $2^32$: $left 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^16+1right$. You will have to look at all the combinations $binom50+binom51+...+binom55=2^5$ and complement with some $varphi(2^n)=2^n-1$ to obtain $2^32$.
edited Aug 11 at 19:30
answered Jul 13 at 8:24
rtybase
8,93721433
8,93721433
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
add a comment |Â
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
Why we are considering Fermat primes specially?
â tarit goswami
Aug 11 at 19:20
1
1
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
@taritgoswami because, as per the comments in brackets, $p_i=2^m_i+1 Rightarrow p_i-1=2^m_i$ which may divide $2^32$, otherwise it's not true.
â rtybase
Aug 11 at 19:27
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2849424%2ffind-solutions-to-varphi-leftn-right-232%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
How about $varphi(17)=2^4$ case?
â rtybase
Jul 13 at 8:07
@rtybase What about it?
â Jon
Jul 13 at 8:09
And any Fermat prime in fact ... What about it? You have quite a few cases to look at ...
â rtybase
Jul 13 at 8:11
@rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 mid 2^32$ but what i'm looking for is to compute solutions to $varphileft(nright)=2^32$, and not just for primes $p$ that satisfy $p-1 mid 2^32$
â Jon
Jul 13 at 8:24
Jon, see my answer ... with a few examples
â rtybase
Jul 13 at 8:26