Mixing
Conjectured primality tests for specific classes of $kcdot b^n pm 1$
$begingroup$
Can you provide proofs or counterexamples for the claims given below?
Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims:
First claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $M= k cdot b^{n}-1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{M}right)=1$ and $left(frac{a+2}{M}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} M$. Then $M$ is prime if and only if $S_{n-2} equiv 0 pmod{M}$ .
You can run this test here .
Second claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}+1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{N}right)=-1$ and $left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
You can run this test here .
I have tested these claims for many random values of $k$, $b$ and $n$ and there were no countereamples.
REMARK
It is possible to reformulate these claims into more compact form:
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}pm 1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{2-a}{N}right)=left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
GUI application that implements these tests can be found here .
A command line program that implements these tests can be found here .
elementary-number-theory prime-numbers examples-counterexamples primality-test lucas-lehmer-test
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
$endgroup$
add a comment |
$begingroup$
Can you provide proofs or counterexamples for the claims given below?
Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims:
First claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $M= k cdot b^{n}-1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{M}right)=1$ and $left(frac{a+2}{M}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} M$. Then $M$ is prime if and only if $S_{n-2} equiv 0 pmod{M}$ .
You can run this test here .
Second claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}+1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{N}right)=-1$ and $left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
You can run this test here .
I have tested these claims for many random values of $k$, $b$ and $n$ and there were no countereamples.
REMARK
It is possible to reformulate these claims into more compact form:
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}pm 1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{2-a}{N}right)=left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
GUI application that implements these tests can be found here .
A command line program that implements these tests can be found here .
elementary-number-theory prime-numbers examples-counterexamples primality-test lucas-lehmer-test
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
$endgroup$
6
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47
add a comment |
$begingroup$
Can you provide proofs or counterexamples for the claims given below?
Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims:
First claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $M= k cdot b^{n}-1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{M}right)=1$ and $left(frac{a+2}{M}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} M$. Then $M$ is prime if and only if $S_{n-2} equiv 0 pmod{M}$ .
You can run this test here .
Second claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}+1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{N}right)=-1$ and $left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
You can run this test here .
I have tested these claims for many random values of $k$, $b$ and $n$ and there were no countereamples.
REMARK
It is possible to reformulate these claims into more compact form:
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}pm 1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{2-a}{N}right)=left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
GUI application that implements these tests can be found here .
A command line program that implements these tests can be found here .
elementary-number-theory prime-numbers examples-counterexamples primality-test lucas-lehmer-test
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
$endgroup$
Can you provide proofs or counterexamples for the claims given below?
Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims:
First claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $M= k cdot b^{n}-1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{M}right)=1$ and $left(frac{a+2}{M}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} M$. Then $M$ is prime if and only if $S_{n-2} equiv 0 pmod{M}$ .
You can run this test here .
Second claim
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}+1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{a-2}{N}right)=-1$ and $left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
You can run this test here .
I have tested these claims for many random values of $k$, $b$ and $n$ and there were no countereamples.
REMARK
It is possible to reformulate these claims into more compact form:
Let $P_m(x)=2^{-m}cdot((x-sqrt{x^2-4})^m+(x+sqrt{x^2-4})^m)$ .
Let $N= k cdot b^{n}pm 1 $ where $k$ is positive natural number , $ k<2^n$ , $b$ is an even positive natural number and $nge3$ . Let $a$ be a natural number greater than two such that $left(frac{2-a}{N}right)=left(frac{a+2}{N}right)=-1$ where $left(frac{}{}right)$ denotes Jacobi symbol. Let $S_i=P_b(S_{i-1})$ with $S_0$ equal to the modular $P_{kb/2}(P_{b/2}(a))phantom{5} text{mod} phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} equiv 0 pmod{N}$ .
GUI application that implements these tests can be found here .
A command line program that implements these tests can be found here .
elementary-number-theory prime-numbers examples-counterexamples primality-test lucas-lehmer-test
elementary-number-theory prime-numbers examples-counterexamples primality-test lucas-lehmer-test
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
edited Mar 27 at 12:48
Peđa Terzić
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
asked Feb 2 at 19:38
Peđa TerzićPeđa Terzić
7,67922674
7,67922674
6
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47
add a comment |
6
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47
6
6
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony
answered Mar 14 at 17:08
Tony ReixTony Reix
777
$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%2f3097702%2fconjectured-primality-tests-for-specific-classes-of-k-cdot-bn-pm-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony
answered Mar 14 at 17:08
Tony ReixTony Reix
777
$endgroup$
add a comment |
$begingroup$
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony
answered Mar 14 at 17:08
Tony ReixTony Reix
777
$endgroup$
add a comment |
$begingroup$
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony
answered Mar 14 at 17:08
Tony ReixTony Reix
777
$endgroup$
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony
answered Mar 14 at 17:08
Tony ReixTony Reix
777
answered Mar 14 at 17:08
Tony ReixTony Reix
777
answered Mar 14 at 17:08
Tony ReixTony Reix
777
answered Mar 14 at 17:08
Tony ReixTony Reix
777
777
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%2f3097702%2fconjectured-primality-tests-for-specific-classes-of-k-cdot-bn-pm-1%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
6
$begingroup$
You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested.
$endgroup$
– vadim123
Feb 4 at 19:47