Determining if $973$ is prime
$begingroup$
Without a calculator, determine if $973$ is prime or not
I was given this question to solve. I know $973$ is not prime. I was told a strategy to solve whether a number is prime or not is to test all the numbers less than the square root of $973$
So I would have to test till $32$
and i find $1,7,139$ and $973$ are factors of this number. Basically, what I want to find out is are there any other strategies to solve this question? then i wouldn't have to check till 1-32 to see if any of the numbers are factors.
prime-numbers
asked Oct 25 '15 at 21:04
mikamika
517212
$endgroup$
|
show 5 more comments
$begingroup$
Without a calculator, determine if $973$ is prime or not
I was given this question to solve. I know $973$ is not prime. I was told a strategy to solve whether a number is prime or not is to test all the numbers less than the square root of $973$
So I would have to test till $32$
and i find $1,7,139$ and $973$ are factors of this number. Basically, what I want to find out is are there any other strategies to solve this question? then i wouldn't have to check till 1-32 to see if any of the numbers are factors.
prime-numbers
asked Oct 25 '15 at 21:04
mikamika
517212
$endgroup$
6
$begingroup$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
1
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
1
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54
|
show 5 more comments
$begingroup$
Without a calculator, determine if $973$ is prime or not
I was given this question to solve. I know $973$ is not prime. I was told a strategy to solve whether a number is prime or not is to test all the numbers less than the square root of $973$
So I would have to test till $32$
and i find $1,7,139$ and $973$ are factors of this number. Basically, what I want to find out is are there any other strategies to solve this question? then i wouldn't have to check till 1-32 to see if any of the numbers are factors.
prime-numbers
asked Oct 25 '15 at 21:04
mikamika
517212
$endgroup$
Without a calculator, determine if $973$ is prime or not
I was given this question to solve. I know $973$ is not prime. I was told a strategy to solve whether a number is prime or not is to test all the numbers less than the square root of $973$
So I would have to test till $32$
and i find $1,7,139$ and $973$ are factors of this number. Basically, what I want to find out is are there any other strategies to solve this question? then i wouldn't have to check till 1-32 to see if any of the numbers are factors.
prime-numbers
prime-numbers
asked Oct 25 '15 at 21:04
mikamika
517212
asked Oct 25 '15 at 21:04
mikamika
517212
asked Oct 25 '15 at 21:04
mikamika
517212
asked Oct 25 '15 at 21:04
mikamika
517212
asked Oct 25 '15 at 21:04
mikamika
517212
517212
6
$begingroup$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
1
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
1
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54
|
show 5 more comments
6
$begingroup$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
1
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
1
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54
6
6
$begingroup$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
1
1
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
1
1
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54
|
show 5 more comments
6 Answers
6
active
oldest
votes
$begingroup$
Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$
Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that
$973=(10)^3-(3)^3=(10-3)(100+9+30)=7cdot139$
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
$endgroup$
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
add a comment |
$begingroup$
Not a clean method though but I used Fermat's factorization to find that,
$(31)^2<973<(32)^2$
Now applying the fact that a perfect square should end only in 0,1,4,5,6,9
, concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.
Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$
Therefore, $973=(73-66)(73+66)=7cdot
139$
Hence $973$ is not a prime.
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
For small numbers, there is no much better strategy than trying all prime divisors up to the square root.
Use divisibility criteria for the tiny divisors.
$2$: check the last digit even;
$3$: compute the sum of the digits (e.g. $975to21to3$);
$5$: last digit must be $0$ or $5$;
$7$: subtract twice the unit digits from the rest of the number (e.g. $973to91to7$);
$11$: subtract the unit digits from the rest of the number (e.g. $2585to253to22$).
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
$endgroup$
add a comment |
$begingroup$
Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then
$a^{p-1} equiv1 mod p$
In this case, we can chose $a$ to be $2$ so as to keep things simple.
It's not hard to see that $(2)^{10}= 1024 equiv51mod973$
Therefore, on applying Fermat's Little Theorem
$(2^{10})^{97}$ . $2^2$ $equiv(51)^{97}.2^2mod 973$ $notequiv1mod 973$
Hence, $973$ is not a prime number
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Another way, $973 = 910+63$
This gives $973 = 7.(130+9) = 7 . 139$
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
If you're good at arithmetic, you can try this without a calculator $:)$
Wilson's theorem:
$p$ prime $iff$ $(p-1)! equiv -1 pmod p$.
Else, pocklington's test could be fast.
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
$endgroup$
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
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%2f1497404%2fdetermining-if-973-is-prime%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$
Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that
$973=(10)^3-(3)^3=(10-3)(100+9+30)=7cdot139$
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
$endgroup$
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
add a comment |
$begingroup$
Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$
Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that
$973=(10)^3-(3)^3=(10-3)(100+9+30)=7cdot139$
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
$endgroup$
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
add a comment |
$begingroup$
Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$
Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that
$973=(10)^3-(3)^3=(10-3)(100+9+30)=7cdot139$
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
$endgroup$
Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$
Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that
$973=(10)^3-(3)^3=(10-3)(100+9+30)=7cdot139$
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
edited Aug 24 '18 at 9:39
Oscar Lanzi
13.6k12136
13.6k12136
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 8:25
naveen dankalnaveen dankal
4,59931348
4,59931348
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
add a comment |
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
$begingroup$
Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
$endgroup$
– Yves Daoust
Aug 24 '18 at 10:01
add a comment |
$begingroup$
Not a clean method though but I used Fermat's factorization to find that,
$(31)^2<973<(32)^2$
Now applying the fact that a perfect square should end only in 0,1,4,5,6,9
, concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.
Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$
Therefore, $973=(73-66)(73+66)=7cdot
139$
Hence $973$ is not a prime.
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Not a clean method though but I used Fermat's factorization to find that,
$(31)^2<973<(32)^2$
Now applying the fact that a perfect square should end only in 0,1,4,5,6,9
, concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.
Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$
Therefore, $973=(73-66)(73+66)=7cdot
139$
Hence $973$ is not a prime.
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Not a clean method though but I used Fermat's factorization to find that,
$(31)^2<973<(32)^2$
Now applying the fact that a perfect square should end only in 0,1,4,5,6,9
, concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.
Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$
Therefore, $973=(73-66)(73+66)=7cdot
139$
Hence $973$ is not a prime.
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
$endgroup$
Not a clean method though but I used Fermat's factorization to find that,
$(31)^2<973<(32)^2$
Now applying the fact that a perfect square should end only in 0,1,4,5,6,9
, concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.
Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$
Therefore, $973=(73-66)(73+66)=7cdot
139$
Hence $973$ is not a prime.
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
edited Aug 24 '18 at 8:52
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 7:49
naveen dankalnaveen dankal
4,59931348
4,59931348
add a comment |
add a comment |
$begingroup$
For small numbers, there is no much better strategy than trying all prime divisors up to the square root.
Use divisibility criteria for the tiny divisors.
$2$: check the last digit even;
$3$: compute the sum of the digits (e.g. $975to21to3$);
$5$: last digit must be $0$ or $5$;
$7$: subtract twice the unit digits from the rest of the number (e.g. $973to91to7$);
$11$: subtract the unit digits from the rest of the number (e.g. $2585to253to22$).
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
$endgroup$
add a comment |
$begingroup$
For small numbers, there is no much better strategy than trying all prime divisors up to the square root.
Use divisibility criteria for the tiny divisors.
$2$: check the last digit even;
$3$: compute the sum of the digits (e.g. $975to21to3$);
$5$: last digit must be $0$ or $5$;
$7$: subtract twice the unit digits from the rest of the number (e.g. $973to91to7$);
$11$: subtract the unit digits from the rest of the number (e.g. $2585to253to22$).
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
$endgroup$
add a comment |
$begingroup$
For small numbers, there is no much better strategy than trying all prime divisors up to the square root.
Use divisibility criteria for the tiny divisors.
$2$: check the last digit even;
$3$: compute the sum of the digits (e.g. $975to21to3$);
$5$: last digit must be $0$ or $5$;
$7$: subtract twice the unit digits from the rest of the number (e.g. $973to91to7$);
$11$: subtract the unit digits from the rest of the number (e.g. $2585to253to22$).
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
$endgroup$
For small numbers, there is no much better strategy than trying all prime divisors up to the square root.
Use divisibility criteria for the tiny divisors.
$2$: check the last digit even;
$3$: compute the sum of the digits (e.g. $975to21to3$);
$5$: last digit must be $0$ or $5$;
$7$: subtract twice the unit digits from the rest of the number (e.g. $973to91to7$);
$11$: subtract the unit digits from the rest of the number (e.g. $2585to253to22$).
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
edited Aug 24 '18 at 9:34
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
answered Aug 24 '18 at 9:29
Yves DaoustYves Daoust
132k676230
132k676230
add a comment |
add a comment |
$begingroup$
Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then
$a^{p-1} equiv1 mod p$
In this case, we can chose $a$ to be $2$ so as to keep things simple.
It's not hard to see that $(2)^{10}= 1024 equiv51mod973$
Therefore, on applying Fermat's Little Theorem
$(2^{10})^{97}$ . $2^2$ $equiv(51)^{97}.2^2mod 973$ $notequiv1mod 973$
Hence, $973$ is not a prime number
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then
$a^{p-1} equiv1 mod p$
In this case, we can chose $a$ to be $2$ so as to keep things simple.
It's not hard to see that $(2)^{10}= 1024 equiv51mod973$
Therefore, on applying Fermat's Little Theorem
$(2^{10})^{97}$ . $2^2$ $equiv(51)^{97}.2^2mod 973$ $notequiv1mod 973$
Hence, $973$ is not a prime number
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then
$a^{p-1} equiv1 mod p$
In this case, we can chose $a$ to be $2$ so as to keep things simple.
It's not hard to see that $(2)^{10}= 1024 equiv51mod973$
Therefore, on applying Fermat's Little Theorem
$(2^{10})^{97}$ . $2^2$ $equiv(51)^{97}.2^2mod 973$ $notequiv1mod 973$
Hence, $973$ is not a prime number
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
$endgroup$
Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then
$a^{p-1} equiv1 mod p$
In this case, we can chose $a$ to be $2$ so as to keep things simple.
It's not hard to see that $(2)^{10}= 1024 equiv51mod973$
Therefore, on applying Fermat's Little Theorem
$(2^{10})^{97}$ . $2^2$ $equiv(51)^{97}.2^2mod 973$ $notequiv1mod 973$
Hence, $973$ is not a prime number
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
answered Aug 24 '18 at 13:09
naveen dankalnaveen dankal
4,59931348
4,59931348
add a comment |
add a comment |
$begingroup$
Another way, $973 = 910+63$
This gives $973 = 7.(130+9) = 7 . 139$
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Another way, $973 = 910+63$
This gives $973 = 7.(130+9) = 7 . 139$
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
$endgroup$
add a comment |
$begingroup$
Another way, $973 = 910+63$
This gives $973 = 7.(130+9) = 7 . 139$
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
$endgroup$
Another way, $973 = 910+63$
This gives $973 = 7.(130+9) = 7 . 139$
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
answered Dec 20 '18 at 8:17
naveen dankalnaveen dankal
4,59931348
4,59931348
add a comment |
add a comment |
$begingroup$
If you're good at arithmetic, you can try this without a calculator $:)$
Wilson's theorem:
$p$ prime $iff$ $(p-1)! equiv -1 pmod p$.
Else, pocklington's test could be fast.
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
$endgroup$
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
add a comment |
$begingroup$
If you're good at arithmetic, you can try this without a calculator $:)$
Wilson's theorem:
$p$ prime $iff$ $(p-1)! equiv -1 pmod p$.
Else, pocklington's test could be fast.
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
$endgroup$
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
add a comment |
$begingroup$
If you're good at arithmetic, you can try this without a calculator $:)$
Wilson's theorem:
$p$ prime $iff$ $(p-1)! equiv -1 pmod p$.
Else, pocklington's test could be fast.
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
$endgroup$
If you're good at arithmetic, you can try this without a calculator $:)$
Wilson's theorem:
$p$ prime $iff$ $(p-1)! equiv -1 pmod p$.
Else, pocklington's test could be fast.
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
edited Oct 25 '15 at 21:28
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
answered Oct 25 '15 at 21:16
YoTengoUnLCDYoTengoUnLCD
7,46332161
7,46332161
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
add a comment |
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
2
2
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
$begingroup$
It's $mod p$, not $mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given.
$endgroup$
– Cataline
Oct 25 '15 at 21:21
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%2f1497404%2fdetermining-if-973-is-prime%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$
It suffices to try primes below $sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ...
$endgroup$
– Hagen von Eitzen
Oct 25 '15 at 21:06
$begingroup$
Do you know the Erathostene's sieve?
$endgroup$
– Emilio Novati
Oct 25 '15 at 21:10
1
$begingroup$
And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
$endgroup$
– Did
Oct 25 '15 at 21:25
1
$begingroup$
One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime.
$endgroup$
– Travis
Oct 25 '15 at 21:38
$begingroup$
@EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
$endgroup$
– mika
Oct 25 '15 at 23:54