Mixing
Checking whether a number is prime or not
up vote
3
down vote
favorite
Is it true that a natural number $n>1$ is prime if and only if $n|left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n-1$?
We know that $11$ is a prime number, but let us assume that we do not know, and let us also assume that the statement is true;
$$left ( frac{1+sqrt{5}}{2} right )^{11}+left ( frac{1-sqrt{5}}{2} right )^{11}-1=198.$$
Clearly, $11|198$. Therefore, as our assumption that the statement is true, the number $11$ is a prime number.
number-theory elementary-number-theory prime-numbers
edited 23 hours ago
Robert Z
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
|
show 2 more comments
up vote
3
down vote
favorite
Is it true that a natural number $n>1$ is prime if and only if $n|left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n-1$?
We know that $11$ is a prime number, but let us assume that we do not know, and let us also assume that the statement is true;
$$left ( frac{1+sqrt{5}}{2} right )^{11}+left ( frac{1-sqrt{5}}{2} right )^{11}-1=198.$$
Clearly, $11|198$. Therefore, as our assumption that the statement is true, the number $11$ is a prime number.
number-theory elementary-number-theory prime-numbers
edited 23 hours ago
Robert Z
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
1
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
1
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago
|
show 2 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Is it true that a natural number $n>1$ is prime if and only if $n|left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n-1$?
We know that $11$ is a prime number, but let us assume that we do not know, and let us also assume that the statement is true;
$$left ( frac{1+sqrt{5}}{2} right )^{11}+left ( frac{1-sqrt{5}}{2} right )^{11}-1=198.$$
Clearly, $11|198$. Therefore, as our assumption that the statement is true, the number $11$ is a prime number.
number-theory elementary-number-theory prime-numbers
edited 23 hours ago
Robert Z
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
Is it true that a natural number $n>1$ is prime if and only if $n|left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n-1$?
We know that $11$ is a prime number, but let us assume that we do not know, and let us also assume that the statement is true;
$$left ( frac{1+sqrt{5}}{2} right )^{11}+left ( frac{1-sqrt{5}}{2} right )^{11}-1=198.$$
Clearly, $11|198$. Therefore, as our assumption that the statement is true, the number $11$ is a prime number.
number-theory elementary-number-theory prime-numbers
number-theory elementary-number-theory prime-numbers
edited 23 hours ago
Robert Z
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
edited 23 hours ago
Robert Z
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
edited 23 hours ago
Robert Z
89.8k1056128
edited 23 hours ago
Robert Z
89.8k1056128
edited 23 hours ago
Robert Z
89.8k1056128
89.8k1056128
asked 23 hours ago
Hussain-Alqatari
1826
asked 23 hours ago
Hussain-Alqatari
1826
asked 23 hours ago
Hussain-Alqatari
1826
1826
1
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
1
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago
|
show 2 more comments
1
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
1
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago
1
1
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
1
1
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago
|
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
4
down vote
Note that $left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n$ is the $n$-th Lucas number.
It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$,
$$L_p-1=frac{1}{2^{p-1}}sum_{k=1}^{(p-1)/2}binom{p}{2k}5^k=0pmod{p}$$
because $p$ divides each $binom{p}{2k}$.
On the contrary $705$ is not a prime but it divides $L_{705}-1$.
See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.
answered 23 hours ago
Robert Z
89.8k1056128
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Note that $left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n$ is the $n$-th Lucas number.
It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$,
$$L_p-1=frac{1}{2^{p-1}}sum_{k=1}^{(p-1)/2}binom{p}{2k}5^k=0pmod{p}$$
because $p$ divides each $binom{p}{2k}$.
On the contrary $705$ is not a prime but it divides $L_{705}-1$.
See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.
answered 23 hours ago
Robert Z
89.8k1056128
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
add a comment |
up vote
4
down vote
Note that $left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n$ is the $n$-th Lucas number.
It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$,
$$L_p-1=frac{1}{2^{p-1}}sum_{k=1}^{(p-1)/2}binom{p}{2k}5^k=0pmod{p}$$
because $p$ divides each $binom{p}{2k}$.
On the contrary $705$ is not a prime but it divides $L_{705}-1$.
See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.
answered 23 hours ago
Robert Z
89.8k1056128
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
add a comment |
up vote
4
down vote
up vote
4
down vote
Note that $left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n$ is the $n$-th Lucas number.
It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$,
$$L_p-1=frac{1}{2^{p-1}}sum_{k=1}^{(p-1)/2}binom{p}{2k}5^k=0pmod{p}$$
because $p$ divides each $binom{p}{2k}$.
On the contrary $705$ is not a prime but it divides $L_{705}-1$.
See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.
answered 23 hours ago
Robert Z
89.8k1056128
Note that $left ( frac{1+sqrt{5}}{2} right )^n+left ( frac{1-sqrt{5}}{2} right )^n$ is the $n$-th Lucas number.
It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$,
$$L_p-1=frac{1}{2^{p-1}}sum_{k=1}^{(p-1)/2}binom{p}{2k}5^k=0pmod{p}$$
because $p$ divides each $binom{p}{2k}$.
On the contrary $705$ is not a prime but it divides $L_{705}-1$.
See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.
answered 23 hours ago
Robert Z
89.8k1056128
edited 23 hours ago
answered 23 hours ago
Robert Z
89.8k1056128
answered 23 hours ago
Robert Z
89.8k1056128
answered 23 hours ago
Robert Z
89.8k1056128
89.8k1056128
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
add a comment |
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
"... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$
– Hussain-Alqatari
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari Sorry, you are right!
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
@Hussain-Alqatari I edited my answer with the proof of the implication that holds..
– Robert Z
23 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test.
– DanaJ
14 hours ago
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004854%2fchecking-whether-a-number-is-prime-or-not%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
1
But $18|198$ and $18$ is not prime.
– saulspatz
23 hours ago
en.wikipedia.org/wiki/…
– lab bhattacharjee
23 hours ago
1
@Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $pmod {71}$ for which all the numbers are small. We get $L_{71}equiv 1 pmod {71}$. as desired. (the numbers we are checking are $L_n-1$)
– lulu
23 hours ago
Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right?
– Russ
23 hours ago
@Russ Yes, that's my understanding.
– lulu
23 hours ago