Generating Prime Numbers From Composite Numbers
up vote
1
down vote
favorite
If $a$ and $b$ are non-perfect-square composite numbers, and $gcd(a,b)=1$,
then at least one element of {$ab-1,ab+1$} is a prime number.
For example, if we let $a=35$, and $b=18$; clearly the are free-square composite numbers, and gcd$(35,18)=1$
$ab-1=35times18-1=629$ which is a composite number, and
$ab+1=35times18+1=631$ which is a prime number.
Is the statement true?
elementary-number-theory prime-numbers
asked Nov 22 at 14:14
Hussain-Alqatari
2977
add a comment |
up vote
1
down vote
favorite
If $a$ and $b$ are non-perfect-square composite numbers, and $gcd(a,b)=1$,
then at least one element of {$ab-1,ab+1$} is a prime number.
For example, if we let $a=35$, and $b=18$; clearly the are free-square composite numbers, and gcd$(35,18)=1$
$ab-1=35times18-1=629$ which is a composite number, and
$ab+1=35times18+1=631$ which is a prime number.
Is the statement true?
elementary-number-theory prime-numbers
asked Nov 22 at 14:14
Hussain-Alqatari
2977
3
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
1
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
If $a$ and $b$ are non-perfect-square composite numbers, and $gcd(a,b)=1$,
then at least one element of {$ab-1,ab+1$} is a prime number.
For example, if we let $a=35$, and $b=18$; clearly the are free-square composite numbers, and gcd$(35,18)=1$
$ab-1=35times18-1=629$ which is a composite number, and
$ab+1=35times18+1=631$ which is a prime number.
Is the statement true?
elementary-number-theory prime-numbers
asked Nov 22 at 14:14
Hussain-Alqatari
2977
If $a$ and $b$ are non-perfect-square composite numbers, and $gcd(a,b)=1$,
then at least one element of {$ab-1,ab+1$} is a prime number.
For example, if we let $a=35$, and $b=18$; clearly the are free-square composite numbers, and gcd$(35,18)=1$
$ab-1=35times18-1=629$ which is a composite number, and
$ab+1=35times18+1=631$ which is a prime number.
Is the statement true?
elementary-number-theory prime-numbers
elementary-number-theory prime-numbers
asked Nov 22 at 14:14
Hussain-Alqatari
2977
asked Nov 22 at 14:14
Hussain-Alqatari
2977
edited Nov 23 at 10:02
asked Nov 22 at 14:14
Hussain-Alqatari
2977
asked Nov 22 at 14:14
Hussain-Alqatari
2977
asked Nov 22 at 14:14
Hussain-Alqatari
2977
2977
3
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
1
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38
add a comment |
3
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
1
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38
3
3
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
1
1
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
You certainly need at least one of $a,b$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $a=38,b=143$, so $ab=5434$. neither $5433$ nor $5435$ is prime.
[edit] As Arthur points out my example is rather larger than necessary. $ab$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $2310$ (which isn't a counterexample). So we can look at the values in this sequence below $2310$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $ab$) few counterexamples. They are:
714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262
answered Nov 22 at 14:29
Especially Lime
21.3k22656
add a comment |
up vote
3
down vote
If both $a$ and $b$ are odd, then $abpm 1$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $a = 34, b = 21$ gives
$$
ab + 1 = 715 = 5cdot 11cdot 13\
ab - 1 = 713 = 23cdot 31
$$
answered Nov 22 at 14:19
Arthur
110k7104186
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
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',
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%2f3009184%2fgenerating-prime-numbers-from-composite-numbers%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
up vote
2
down vote
accepted
You certainly need at least one of $a,b$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $a=38,b=143$, so $ab=5434$. neither $5433$ nor $5435$ is prime.
[edit] As Arthur points out my example is rather larger than necessary. $ab$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $2310$ (which isn't a counterexample). So we can look at the values in this sequence below $2310$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $ab$) few counterexamples. They are:
714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262
answered Nov 22 at 14:29
Especially Lime
21.3k22656
add a comment |
up vote
2
down vote
accepted
You certainly need at least one of $a,b$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $a=38,b=143$, so $ab=5434$. neither $5433$ nor $5435$ is prime.
[edit] As Arthur points out my example is rather larger than necessary. $ab$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $2310$ (which isn't a counterexample). So we can look at the values in this sequence below $2310$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $ab$) few counterexamples. They are:
714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262
answered Nov 22 at 14:29
Especially Lime
21.3k22656
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
You certainly need at least one of $a,b$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $a=38,b=143$, so $ab=5434$. neither $5433$ nor $5435$ is prime.
[edit] As Arthur points out my example is rather larger than necessary. $ab$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $2310$ (which isn't a counterexample). So we can look at the values in this sequence below $2310$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $ab$) few counterexamples. They are:
714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262
answered Nov 22 at 14:29
Especially Lime
21.3k22656
You certainly need at least one of $a,b$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $a=38,b=143$, so $ab=5434$. neither $5433$ nor $5435$ is prime.
[edit] As Arthur points out my example is rather larger than necessary. $ab$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $2310$ (which isn't a counterexample). So we can look at the values in this sequence below $2310$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $ab$) few counterexamples. They are:
714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262
answered Nov 22 at 14:29
Especially Lime
21.3k22656
edited Nov 23 at 9:35
answered Nov 22 at 14:29
Especially Lime
21.3k22656
answered Nov 22 at 14:29
Especially Lime
21.3k22656
answered Nov 22 at 14:29
Especially Lime
21.3k22656
21.3k22656
add a comment |
add a comment |
up vote
3
down vote
If both $a$ and $b$ are odd, then $abpm 1$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $a = 34, b = 21$ gives
$$
ab + 1 = 715 = 5cdot 11cdot 13\
ab - 1 = 713 = 23cdot 31
$$
answered Nov 22 at 14:19
Arthur
110k7104186
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
add a comment |
up vote
3
down vote
If both $a$ and $b$ are odd, then $abpm 1$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $a = 34, b = 21$ gives
$$
ab + 1 = 715 = 5cdot 11cdot 13\
ab - 1 = 713 = 23cdot 31
$$
answered Nov 22 at 14:19
Arthur
110k7104186
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
add a comment |
up vote
3
down vote
up vote
3
down vote
If both $a$ and $b$ are odd, then $abpm 1$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $a = 34, b = 21$ gives
$$
ab + 1 = 715 = 5cdot 11cdot 13\
ab - 1 = 713 = 23cdot 31
$$
answered Nov 22 at 14:19
Arthur
110k7104186
If both $a$ and $b$ are odd, then $abpm 1$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $a = 34, b = 21$ gives
$$
ab + 1 = 715 = 5cdot 11cdot 13\
ab - 1 = 713 = 23cdot 31
$$
answered Nov 22 at 14:19
Arthur
110k7104186
edited Nov 22 at 14:29
answered Nov 22 at 14:19
Arthur
110k7104186
answered Nov 22 at 14:19
Arthur
110k7104186
answered Nov 22 at 14:19
Arthur
110k7104186
110k7104186
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
add a comment |
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
1
1
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
$a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though.
– Especially Lime
Nov 22 at 14:23
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
@EspeciallyLime I found a (hopefully correct this time) example. (Wonder if it's the smallest...)
– Arthur
Nov 22 at 14:30
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3009184%2fgenerating-prime-numbers-from-composite-numbers%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
3
$18 = 3^2cdot 2$ is not square-free.
– Arthur
Nov 22 at 14:16
1
If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample.
– Arthur
Nov 22 at 14:38