Mixing
Find all values such that $phi(n)=n-2$
$begingroup$
I'm currently working in the following Euler's theorem exercise:
Find all values such that $phi(n)=n-2$
A simple calculation gave me the first one based on the formula $phi(n^k) = n^k-n^{k-1}$, so with $n=4$, checking similar questions here I'm trying to find other numbers based on:
$$phi(n)=nprod_{p|n}(1-1/p)$$
But I've been unable to use it to solve my problem, any help will be really appreciated.
elementary-number-theory modular-arithmetic
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
$endgroup$
add a comment |
$begingroup$
I'm currently working in the following Euler's theorem exercise:
Find all values such that $phi(n)=n-2$
A simple calculation gave me the first one based on the formula $phi(n^k) = n^k-n^{k-1}$, so with $n=4$, checking similar questions here I'm trying to find other numbers based on:
$$phi(n)=nprod_{p|n}(1-1/p)$$
But I've been unable to use it to solve my problem, any help will be really appreciated.
elementary-number-theory modular-arithmetic
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
$endgroup$
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33
add a comment |
$begingroup$
I'm currently working in the following Euler's theorem exercise:
Find all values such that $phi(n)=n-2$
A simple calculation gave me the first one based on the formula $phi(n^k) = n^k-n^{k-1}$, so with $n=4$, checking similar questions here I'm trying to find other numbers based on:
$$phi(n)=nprod_{p|n}(1-1/p)$$
But I've been unable to use it to solve my problem, any help will be really appreciated.
elementary-number-theory modular-arithmetic
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
$endgroup$
I'm currently working in the following Euler's theorem exercise:
Find all values such that $phi(n)=n-2$
A simple calculation gave me the first one based on the formula $phi(n^k) = n^k-n^{k-1}$, so with $n=4$, checking similar questions here I'm trying to find other numbers based on:
$$phi(n)=nprod_{p|n}(1-1/p)$$
But I've been unable to use it to solve my problem, any help will be really appreciated.
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
edited Feb 3 at 7:14
Jyrki Lahtonen
110k13172392
110k13172392
asked Feb 3 at 0:04
mrazmraz
452110
asked Feb 3 at 0:04
mrazmraz
452110
asked Feb 3 at 0:04
mrazmraz
452110
452110
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33
add a comment |
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If $phi(n)=n-2$, there are exactly two integers between $2$ and $n$ that have a common factor with $n$. For $n>1$ (which we obviously need), $n$ is one of them. That leaves one other.
If $n$ is prime, then there are no others and $phi(n)=n-1$. Nope.
If $n$ is not prime, there's some prime $p<n$ such that $p|n$. Then $p$ and $frac np$ both have a common factor with $n$, and are both different from $n$. If $pneq frac np$, that's three integers with a common factor right there. Nope.
That leaves the case $n=p^2$ for $p$ a prime. In this case, we can easily see that $phi(p^2)=p^2-p$, leaving $p=2$ and $n=4$ the only option. There is only one solution to $phi(n)=n-2$, namely $n=4$.
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
$begingroup$
If $phi(n)=n-2$ and $q$ is a prime divisor of $n$, then
$$n-2=phi(n)=nprod_{pmid n}(1-1/p)le n(1-1/q)=n-{nover q}$$
which implies $nle2q$. This in turn implies either $n=q$ or $n=2q$. But if $n=q$, then $phi(n)=n-1$, not $n-2$, and if $n=2q$ with $qnot=2$, then $phi(n)=q-1not=2(q-1)=n-2$. The only remaining possibility is $n=2q$ with $q=2$.
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097979%2ffind-all-values-such-that-phin-n-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If $phi(n)=n-2$, there are exactly two integers between $2$ and $n$ that have a common factor with $n$. For $n>1$ (which we obviously need), $n$ is one of them. That leaves one other.
If $n$ is prime, then there are no others and $phi(n)=n-1$. Nope.
If $n$ is not prime, there's some prime $p<n$ such that $p|n$. Then $p$ and $frac np$ both have a common factor with $n$, and are both different from $n$. If $pneq frac np$, that's three integers with a common factor right there. Nope.
That leaves the case $n=p^2$ for $p$ a prime. In this case, we can easily see that $phi(p^2)=p^2-p$, leaving $p=2$ and $n=4$ the only option. There is only one solution to $phi(n)=n-2$, namely $n=4$.
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
$begingroup$
If $phi(n)=n-2$, there are exactly two integers between $2$ and $n$ that have a common factor with $n$. For $n>1$ (which we obviously need), $n$ is one of them. That leaves one other.
If $n$ is prime, then there are no others and $phi(n)=n-1$. Nope.
If $n$ is not prime, there's some prime $p<n$ such that $p|n$. Then $p$ and $frac np$ both have a common factor with $n$, and are both different from $n$. If $pneq frac np$, that's three integers with a common factor right there. Nope.
That leaves the case $n=p^2$ for $p$ a prime. In this case, we can easily see that $phi(p^2)=p^2-p$, leaving $p=2$ and $n=4$ the only option. There is only one solution to $phi(n)=n-2$, namely $n=4$.
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
$begingroup$
If $phi(n)=n-2$, there are exactly two integers between $2$ and $n$ that have a common factor with $n$. For $n>1$ (which we obviously need), $n$ is one of them. That leaves one other.
If $n$ is prime, then there are no others and $phi(n)=n-1$. Nope.
If $n$ is not prime, there's some prime $p<n$ such that $p|n$. Then $p$ and $frac np$ both have a common factor with $n$, and are both different from $n$. If $pneq frac np$, that's three integers with a common factor right there. Nope.
That leaves the case $n=p^2$ for $p$ a prime. In this case, we can easily see that $phi(p^2)=p^2-p$, leaving $p=2$ and $n=4$ the only option. There is only one solution to $phi(n)=n-2$, namely $n=4$.
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
$endgroup$
If $phi(n)=n-2$, there are exactly two integers between $2$ and $n$ that have a common factor with $n$. For $n>1$ (which we obviously need), $n$ is one of them. That leaves one other.
If $n$ is prime, then there are no others and $phi(n)=n-1$. Nope.
If $n$ is not prime, there's some prime $p<n$ such that $p|n$. Then $p$ and $frac np$ both have a common factor with $n$, and are both different from $n$. If $pneq frac np$, that's three integers with a common factor right there. Nope.
That leaves the case $n=p^2$ for $p$ a prime. In this case, we can easily see that $phi(p^2)=p^2-p$, leaving $p=2$ and $n=4$ the only option. There is only one solution to $phi(n)=n-2$, namely $n=4$.
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
answered Feb 3 at 0:38
jmerryjmerry
17.1k11633
17.1k11633
add a comment |
add a comment |
$begingroup$
If $phi(n)=n-2$ and $q$ is a prime divisor of $n$, then
$$n-2=phi(n)=nprod_{pmid n}(1-1/p)le n(1-1/q)=n-{nover q}$$
which implies $nle2q$. This in turn implies either $n=q$ or $n=2q$. But if $n=q$, then $phi(n)=n-1$, not $n-2$, and if $n=2q$ with $qnot=2$, then $phi(n)=q-1not=2(q-1)=n-2$. The only remaining possibility is $n=2q$ with $q=2$.
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
$endgroup$
add a comment |
$begingroup$
If $phi(n)=n-2$ and $q$ is a prime divisor of $n$, then
$$n-2=phi(n)=nprod_{pmid n}(1-1/p)le n(1-1/q)=n-{nover q}$$
which implies $nle2q$. This in turn implies either $n=q$ or $n=2q$. But if $n=q$, then $phi(n)=n-1$, not $n-2$, and if $n=2q$ with $qnot=2$, then $phi(n)=q-1not=2(q-1)=n-2$. The only remaining possibility is $n=2q$ with $q=2$.
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
$endgroup$
add a comment |
$begingroup$
If $phi(n)=n-2$ and $q$ is a prime divisor of $n$, then
$$n-2=phi(n)=nprod_{pmid n}(1-1/p)le n(1-1/q)=n-{nover q}$$
which implies $nle2q$. This in turn implies either $n=q$ or $n=2q$. But if $n=q$, then $phi(n)=n-1$, not $n-2$, and if $n=2q$ with $qnot=2$, then $phi(n)=q-1not=2(q-1)=n-2$. The only remaining possibility is $n=2q$ with $q=2$.
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
$endgroup$
If $phi(n)=n-2$ and $q$ is a prime divisor of $n$, then
$$n-2=phi(n)=nprod_{pmid n}(1-1/p)le n(1-1/q)=n-{nover q}$$
which implies $nle2q$. This in turn implies either $n=q$ or $n=2q$. But if $n=q$, then $phi(n)=n-1$, not $n-2$, and if $n=2q$ with $qnot=2$, then $phi(n)=q-1not=2(q-1)=n-2$. The only remaining possibility is $n=2q$ with $q=2$.
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
answered Feb 3 at 0:51
Barry CipraBarry Cipra
60.7k655129
60.7k655129
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097979%2ffind-all-values-such-that-phin-n-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Note: I'm actually not clear what your question is. The question about $varphi(n)=98$ is a duplicate. But the body of your post appears to be about something entirely different.
$endgroup$
– lulu
Feb 3 at 0:08
$begingroup$
It looks as if $4$ is the only solution; but I don't have a proof.
$endgroup$
– Chris Custer
Feb 3 at 0:33