Mixing
Prove $n$ having to be an exponent of 2 for $b^n + 1 =$ a prime number
$begingroup$
I have been having problems finding a solution for this problem and honestly have no ideas left how to solve this, please help.
Assume that $b^n + 1= $ a prime number for some integers $b,n$ where $b>1$ and $n>1$. Prove that $n$ must take the form $n=2^k$ for some positive integers $k$
What i have been looking at are the generalized Fermat numbers due to $b^n + 1$ taking the form ${b^2}^k + 1$ for $n=2^k$ and Fermat's little theorem but seemingly without any progress.
number-theory prime-numbers fermat-numbers
edited Jan 30 at 0:24
TPace
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
$endgroup$
add a comment |
$begingroup$
I have been having problems finding a solution for this problem and honestly have no ideas left how to solve this, please help.
Assume that $b^n + 1= $ a prime number for some integers $b,n$ where $b>1$ and $n>1$. Prove that $n$ must take the form $n=2^k$ for some positive integers $k$
What i have been looking at are the generalized Fermat numbers due to $b^n + 1$ taking the form ${b^2}^k + 1$ for $n=2^k$ and Fermat's little theorem but seemingly without any progress.
number-theory prime-numbers fermat-numbers
edited Jan 30 at 0:24
TPace
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
$endgroup$
$begingroup$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01
add a comment |
$begingroup$
I have been having problems finding a solution for this problem and honestly have no ideas left how to solve this, please help.
Assume that $b^n + 1= $ a prime number for some integers $b,n$ where $b>1$ and $n>1$. Prove that $n$ must take the form $n=2^k$ for some positive integers $k$
What i have been looking at are the generalized Fermat numbers due to $b^n + 1$ taking the form ${b^2}^k + 1$ for $n=2^k$ and Fermat's little theorem but seemingly without any progress.
number-theory prime-numbers fermat-numbers
edited Jan 30 at 0:24
TPace
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
$endgroup$
I have been having problems finding a solution for this problem and honestly have no ideas left how to solve this, please help.
Assume that $b^n + 1= $ a prime number for some integers $b,n$ where $b>1$ and $n>1$. Prove that $n$ must take the form $n=2^k$ for some positive integers $k$
What i have been looking at are the generalized Fermat numbers due to $b^n + 1$ taking the form ${b^2}^k + 1$ for $n=2^k$ and Fermat's little theorem but seemingly without any progress.
number-theory prime-numbers fermat-numbers
number-theory prime-numbers fermat-numbers
edited Jan 30 at 0:24
TPace
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
edited Jan 30 at 0:24
TPace
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
edited Jan 30 at 0:24
TPace
5111318
edited Jan 30 at 0:24
TPace
5111318
edited Jan 30 at 0:24
TPace
5111318
5111318
asked Jan 30 at 0:12
RyxoRyxo
204
asked Jan 30 at 0:12
RyxoRyxo
204
asked Jan 30 at 0:12
RyxoRyxo
204
204
$begingroup$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01
add a comment |
$begingroup$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01
$begingroup$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01
$begingroup$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If $n$ is an odd natural number then $-1$ is a root of the polynomial $P(x)=x^n+1$ and hence $x+1|x^n+1$.
Now suppose $b^n+1$ is prime and using prime decomposition write $n=2^rm$ when $m$ is odd. Then $b^n+1=(b^{2^r})^m+1$ and hence $b^{2^r}+1|b^n+1$. But we supposed $b^n+1$ is prime so from here we conclude that $b^{2^r}+1=b^n+1$. This implies $n=2^r$.
answered Jan 30 at 0:24
MarkMark
10.4k1622
$endgroup$
add a comment |
$begingroup$
Suppose that $b^n+1$ is prime, $b>1$ and $n>1$. We shall show that $n$ has no odd factor except for $1$: this proves that $n$ is a power of $2$.
So, let $n=st$ where $s,t$ are positive integers and $s$ is odd. You should know the factorisation
$$x^s+1=(x+1)(x^{s-1}-x^{s-2}+cdots-x+1) .$$
Substituting $x=b^t$ shows that $b^t+1$ is a factor of $b^n+1$. But $b^n+1$ is prime, so there are two options:
$$b^t+1=1quadhbox{or}quad b^t+1=b^n+1 .$$
The first is clearly impossible since $b>1$; and the second gives $t=n$, hence $s=1$. We have shown that that only possible odd factor of $n$ is $1$, and as explained above, this means that $n$ is a power of $2$.
answered Jan 30 at 0:27
DavidDavid
69.7k668131
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3092926%2fprove-n-having-to-be-an-exponent-of-2-for-bn-1-a-prime-number%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 $n$ is an odd natural number then $-1$ is a root of the polynomial $P(x)=x^n+1$ and hence $x+1|x^n+1$.
Now suppose $b^n+1$ is prime and using prime decomposition write $n=2^rm$ when $m$ is odd. Then $b^n+1=(b^{2^r})^m+1$ and hence $b^{2^r}+1|b^n+1$. But we supposed $b^n+1$ is prime so from here we conclude that $b^{2^r}+1=b^n+1$. This implies $n=2^r$.
answered Jan 30 at 0:24
MarkMark
10.4k1622
$endgroup$
add a comment |
$begingroup$
If $n$ is an odd natural number then $-1$ is a root of the polynomial $P(x)=x^n+1$ and hence $x+1|x^n+1$.
Now suppose $b^n+1$ is prime and using prime decomposition write $n=2^rm$ when $m$ is odd. Then $b^n+1=(b^{2^r})^m+1$ and hence $b^{2^r}+1|b^n+1$. But we supposed $b^n+1$ is prime so from here we conclude that $b^{2^r}+1=b^n+1$. This implies $n=2^r$.
answered Jan 30 at 0:24
MarkMark
10.4k1622
$endgroup$
add a comment |
$begingroup$
If $n$ is an odd natural number then $-1$ is a root of the polynomial $P(x)=x^n+1$ and hence $x+1|x^n+1$.
Now suppose $b^n+1$ is prime and using prime decomposition write $n=2^rm$ when $m$ is odd. Then $b^n+1=(b^{2^r})^m+1$ and hence $b^{2^r}+1|b^n+1$. But we supposed $b^n+1$ is prime so from here we conclude that $b^{2^r}+1=b^n+1$. This implies $n=2^r$.
answered Jan 30 at 0:24
MarkMark
10.4k1622
$endgroup$
If $n$ is an odd natural number then $-1$ is a root of the polynomial $P(x)=x^n+1$ and hence $x+1|x^n+1$.
Now suppose $b^n+1$ is prime and using prime decomposition write $n=2^rm$ when $m$ is odd. Then $b^n+1=(b^{2^r})^m+1$ and hence $b^{2^r}+1|b^n+1$. But we supposed $b^n+1$ is prime so from here we conclude that $b^{2^r}+1=b^n+1$. This implies $n=2^r$.
answered Jan 30 at 0:24
MarkMark
10.4k1622
answered Jan 30 at 0:24
MarkMark
10.4k1622
answered Jan 30 at 0:24
MarkMark
10.4k1622
answered Jan 30 at 0:24
MarkMark
10.4k1622
10.4k1622
add a comment |
add a comment |
$begingroup$
Suppose that $b^n+1$ is prime, $b>1$ and $n>1$. We shall show that $n$ has no odd factor except for $1$: this proves that $n$ is a power of $2$.
So, let $n=st$ where $s,t$ are positive integers and $s$ is odd. You should know the factorisation
$$x^s+1=(x+1)(x^{s-1}-x^{s-2}+cdots-x+1) .$$
Substituting $x=b^t$ shows that $b^t+1$ is a factor of $b^n+1$. But $b^n+1$ is prime, so there are two options:
$$b^t+1=1quadhbox{or}quad b^t+1=b^n+1 .$$
The first is clearly impossible since $b>1$; and the second gives $t=n$, hence $s=1$. We have shown that that only possible odd factor of $n$ is $1$, and as explained above, this means that $n$ is a power of $2$.
answered Jan 30 at 0:27
DavidDavid
69.7k668131
$endgroup$
add a comment |
$begingroup$
Suppose that $b^n+1$ is prime, $b>1$ and $n>1$. We shall show that $n$ has no odd factor except for $1$: this proves that $n$ is a power of $2$.
So, let $n=st$ where $s,t$ are positive integers and $s$ is odd. You should know the factorisation
$$x^s+1=(x+1)(x^{s-1}-x^{s-2}+cdots-x+1) .$$
Substituting $x=b^t$ shows that $b^t+1$ is a factor of $b^n+1$. But $b^n+1$ is prime, so there are two options:
$$b^t+1=1quadhbox{or}quad b^t+1=b^n+1 .$$
The first is clearly impossible since $b>1$; and the second gives $t=n$, hence $s=1$. We have shown that that only possible odd factor of $n$ is $1$, and as explained above, this means that $n$ is a power of $2$.
answered Jan 30 at 0:27
DavidDavid
69.7k668131
$endgroup$
add a comment |
$begingroup$
Suppose that $b^n+1$ is prime, $b>1$ and $n>1$. We shall show that $n$ has no odd factor except for $1$: this proves that $n$ is a power of $2$.
So, let $n=st$ where $s,t$ are positive integers and $s$ is odd. You should know the factorisation
$$x^s+1=(x+1)(x^{s-1}-x^{s-2}+cdots-x+1) .$$
Substituting $x=b^t$ shows that $b^t+1$ is a factor of $b^n+1$. But $b^n+1$ is prime, so there are two options:
$$b^t+1=1quadhbox{or}quad b^t+1=b^n+1 .$$
The first is clearly impossible since $b>1$; and the second gives $t=n$, hence $s=1$. We have shown that that only possible odd factor of $n$ is $1$, and as explained above, this means that $n$ is a power of $2$.
answered Jan 30 at 0:27
DavidDavid
69.7k668131
$endgroup$
Suppose that $b^n+1$ is prime, $b>1$ and $n>1$. We shall show that $n$ has no odd factor except for $1$: this proves that $n$ is a power of $2$.
So, let $n=st$ where $s,t$ are positive integers and $s$ is odd. You should know the factorisation
$$x^s+1=(x+1)(x^{s-1}-x^{s-2}+cdots-x+1) .$$
Substituting $x=b^t$ shows that $b^t+1$ is a factor of $b^n+1$. But $b^n+1$ is prime, so there are two options:
$$b^t+1=1quadhbox{or}quad b^t+1=b^n+1 .$$
The first is clearly impossible since $b>1$; and the second gives $t=n$, hence $s=1$. We have shown that that only possible odd factor of $n$ is $1$, and as explained above, this means that $n$ is a power of $2$.
answered Jan 30 at 0:27
DavidDavid
69.7k668131
answered Jan 30 at 0:27
DavidDavid
69.7k668131
answered Jan 30 at 0:27
DavidDavid
69.7k668131
answered Jan 30 at 0:27
DavidDavid
69.7k668131
69.7k668131
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%2f3092926%2fprove-n-having-to-be-an-exponent-of-2-for-bn-1-a-prime-number%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$
See this question, three days ago.
$endgroup$
– Dietrich Burde
Jan 30 at 18:01