Mixing
What are the last three non-zero digits of $2015!$?
$begingroup$
What are the last three non-zero digits of $2015!$
I feel confused, I've tried with mod $1000$, but it's useless.
elementary-number-theory
edited Dec 25 '16 at 7:18
Alex
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
$endgroup$
add a comment |
$begingroup$
What are the last three non-zero digits of $2015!$
I feel confused, I've tried with mod $1000$, but it's useless.
elementary-number-theory
edited Dec 25 '16 at 7:18
Alex
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
$endgroup$
$begingroup$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
1
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32
add a comment |
$begingroup$
What are the last three non-zero digits of $2015!$
I feel confused, I've tried with mod $1000$, but it's useless.
elementary-number-theory
edited Dec 25 '16 at 7:18
Alex
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
$endgroup$
What are the last three non-zero digits of $2015!$
I feel confused, I've tried with mod $1000$, but it's useless.
elementary-number-theory
elementary-number-theory
edited Dec 25 '16 at 7:18
Alex
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
edited Dec 25 '16 at 7:18
Alex
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
edited Dec 25 '16 at 7:18
Alex
4,2251628
edited Dec 25 '16 at 7:18
Alex
4,2251628
edited Dec 25 '16 at 7:18
Alex
4,2251628
4,2251628
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
asked Dec 23 '16 at 2:55
Parnaek SiagianParnaek Siagian
162
162
$begingroup$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
1
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32
add a comment |
$begingroup$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
1
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32
$begingroup$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
$begingroup$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
1
1
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It is definitely doable without a computer or calculator, with a small computational effort (less than $100$ multiplications modulo $125$)
The numbers of trailing zeros in $2015!$ is equal to the exponent of $5$ in its factorization (since $2$ has a much larger exponent than $5$), which is:
$$lfloor2015/5rfloor+lfloor2015/5^2rfloor+...=403+80+16+3=502$$
If $x=frac{2015!}{5^{502}}$, all the difficulty is to calculate $xbmod 5^3$. If we would know $xbmod 5^3$, then $2^{502}bmod 5^3=4$ (follows easily from Euler's theorem $2^{100} bmod 5^3=1)$, and its inverse modulo $5^3$ (using for example $4cdot 31=-1 bmod 5^3$).
This would give us the value of $frac{2015!}{10^{502}}bmod 5^3$. As we already know that $frac{2015!}{10^{502}}bmod 2^3=0$, the value of $frac{2015!}{10^{502}}bmod 1000$ would follow by the CRT.
To calculate $xbmod 5^3$, we can use Gauss's generalization of Wilson's theorem. This gives $$prod_{substack{i=1\ 5nmid i}}^{5^3} i equiv -1 pmod {5^3}$$
So we can get rid of entire chunks of $125$ elements
We can get rid first of $2001cdot...cdot2015$. This gives $5^3$, and the rest of the factors are congruent to $74$ modulo $5^3$
From $2000!$ we can take out $5^{400}$, the product of the terms which are not divisible by $5$ is $1bmod 5^3$ (Gauss), and we are left with $400!$
From $400!$ we can take out $5^{80}$, Gauss's theorem gives the product of the terms non-divisible by $5$ up to $375$ as being $-1bmod 5^3$, and all that is left is to calculate $376cdot377cdot378cdot379cdot381cdot...cdot399bmod 5^3$. Then we are left with $80!$
From $80!$ we can take out $5^{16}$. For the product $y$ of the terms non-divisible by $5$, we can calculate first $z=81cdot82cdot83cdot84cdot86cdot...cdot124$ and solve $ycdot zequiv -1 pmod {5^3}$
Then $16!$ is manageable.
There may be more shortcuts that I haven't seen, and/or stronger theorems in number theory, but this is how I would have approached this problem, should I have lived a century ago.
edited Jan 2 at 9:20
Community♦
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
$endgroup$
add a comment |
$begingroup$
The last three non-zero digits are 544 (followed by 502 zeros).
Computed using the online Big Integer Calculator.
Here is a one-line program avoiding large numbers:
m=1;for(k=2,2015,m=m*k;while(m%10==0,m=m/10);m=m%1000);print(m)
(PARI/GP)
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
$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%2f2069177%2fwhat-are-the-last-three-non-zero-digits-of-2015%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$
It is definitely doable without a computer or calculator, with a small computational effort (less than $100$ multiplications modulo $125$)
The numbers of trailing zeros in $2015!$ is equal to the exponent of $5$ in its factorization (since $2$ has a much larger exponent than $5$), which is:
$$lfloor2015/5rfloor+lfloor2015/5^2rfloor+...=403+80+16+3=502$$
If $x=frac{2015!}{5^{502}}$, all the difficulty is to calculate $xbmod 5^3$. If we would know $xbmod 5^3$, then $2^{502}bmod 5^3=4$ (follows easily from Euler's theorem $2^{100} bmod 5^3=1)$, and its inverse modulo $5^3$ (using for example $4cdot 31=-1 bmod 5^3$).
This would give us the value of $frac{2015!}{10^{502}}bmod 5^3$. As we already know that $frac{2015!}{10^{502}}bmod 2^3=0$, the value of $frac{2015!}{10^{502}}bmod 1000$ would follow by the CRT.
To calculate $xbmod 5^3$, we can use Gauss's generalization of Wilson's theorem. This gives $$prod_{substack{i=1\ 5nmid i}}^{5^3} i equiv -1 pmod {5^3}$$
So we can get rid of entire chunks of $125$ elements
We can get rid first of $2001cdot...cdot2015$. This gives $5^3$, and the rest of the factors are congruent to $74$ modulo $5^3$
From $2000!$ we can take out $5^{400}$, the product of the terms which are not divisible by $5$ is $1bmod 5^3$ (Gauss), and we are left with $400!$
From $400!$ we can take out $5^{80}$, Gauss's theorem gives the product of the terms non-divisible by $5$ up to $375$ as being $-1bmod 5^3$, and all that is left is to calculate $376cdot377cdot378cdot379cdot381cdot...cdot399bmod 5^3$. Then we are left with $80!$
From $80!$ we can take out $5^{16}$. For the product $y$ of the terms non-divisible by $5$, we can calculate first $z=81cdot82cdot83cdot84cdot86cdot...cdot124$ and solve $ycdot zequiv -1 pmod {5^3}$
Then $16!$ is manageable.
There may be more shortcuts that I haven't seen, and/or stronger theorems in number theory, but this is how I would have approached this problem, should I have lived a century ago.
edited Jan 2 at 9:20
Community♦
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
$endgroup$
add a comment |
$begingroup$
It is definitely doable without a computer or calculator, with a small computational effort (less than $100$ multiplications modulo $125$)
The numbers of trailing zeros in $2015!$ is equal to the exponent of $5$ in its factorization (since $2$ has a much larger exponent than $5$), which is:
$$lfloor2015/5rfloor+lfloor2015/5^2rfloor+...=403+80+16+3=502$$
If $x=frac{2015!}{5^{502}}$, all the difficulty is to calculate $xbmod 5^3$. If we would know $xbmod 5^3$, then $2^{502}bmod 5^3=4$ (follows easily from Euler's theorem $2^{100} bmod 5^3=1)$, and its inverse modulo $5^3$ (using for example $4cdot 31=-1 bmod 5^3$).
This would give us the value of $frac{2015!}{10^{502}}bmod 5^3$. As we already know that $frac{2015!}{10^{502}}bmod 2^3=0$, the value of $frac{2015!}{10^{502}}bmod 1000$ would follow by the CRT.
To calculate $xbmod 5^3$, we can use Gauss's generalization of Wilson's theorem. This gives $$prod_{substack{i=1\ 5nmid i}}^{5^3} i equiv -1 pmod {5^3}$$
So we can get rid of entire chunks of $125$ elements
We can get rid first of $2001cdot...cdot2015$. This gives $5^3$, and the rest of the factors are congruent to $74$ modulo $5^3$
From $2000!$ we can take out $5^{400}$, the product of the terms which are not divisible by $5$ is $1bmod 5^3$ (Gauss), and we are left with $400!$
From $400!$ we can take out $5^{80}$, Gauss's theorem gives the product of the terms non-divisible by $5$ up to $375$ as being $-1bmod 5^3$, and all that is left is to calculate $376cdot377cdot378cdot379cdot381cdot...cdot399bmod 5^3$. Then we are left with $80!$
From $80!$ we can take out $5^{16}$. For the product $y$ of the terms non-divisible by $5$, we can calculate first $z=81cdot82cdot83cdot84cdot86cdot...cdot124$ and solve $ycdot zequiv -1 pmod {5^3}$
Then $16!$ is manageable.
There may be more shortcuts that I haven't seen, and/or stronger theorems in number theory, but this is how I would have approached this problem, should I have lived a century ago.
edited Jan 2 at 9:20
Community♦
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
$endgroup$
add a comment |
$begingroup$
It is definitely doable without a computer or calculator, with a small computational effort (less than $100$ multiplications modulo $125$)
The numbers of trailing zeros in $2015!$ is equal to the exponent of $5$ in its factorization (since $2$ has a much larger exponent than $5$), which is:
$$lfloor2015/5rfloor+lfloor2015/5^2rfloor+...=403+80+16+3=502$$
If $x=frac{2015!}{5^{502}}$, all the difficulty is to calculate $xbmod 5^3$. If we would know $xbmod 5^3$, then $2^{502}bmod 5^3=4$ (follows easily from Euler's theorem $2^{100} bmod 5^3=1)$, and its inverse modulo $5^3$ (using for example $4cdot 31=-1 bmod 5^3$).
This would give us the value of $frac{2015!}{10^{502}}bmod 5^3$. As we already know that $frac{2015!}{10^{502}}bmod 2^3=0$, the value of $frac{2015!}{10^{502}}bmod 1000$ would follow by the CRT.
To calculate $xbmod 5^3$, we can use Gauss's generalization of Wilson's theorem. This gives $$prod_{substack{i=1\ 5nmid i}}^{5^3} i equiv -1 pmod {5^3}$$
So we can get rid of entire chunks of $125$ elements
We can get rid first of $2001cdot...cdot2015$. This gives $5^3$, and the rest of the factors are congruent to $74$ modulo $5^3$
From $2000!$ we can take out $5^{400}$, the product of the terms which are not divisible by $5$ is $1bmod 5^3$ (Gauss), and we are left with $400!$
From $400!$ we can take out $5^{80}$, Gauss's theorem gives the product of the terms non-divisible by $5$ up to $375$ as being $-1bmod 5^3$, and all that is left is to calculate $376cdot377cdot378cdot379cdot381cdot...cdot399bmod 5^3$. Then we are left with $80!$
From $80!$ we can take out $5^{16}$. For the product $y$ of the terms non-divisible by $5$, we can calculate first $z=81cdot82cdot83cdot84cdot86cdot...cdot124$ and solve $ycdot zequiv -1 pmod {5^3}$
Then $16!$ is manageable.
There may be more shortcuts that I haven't seen, and/or stronger theorems in number theory, but this is how I would have approached this problem, should I have lived a century ago.
edited Jan 2 at 9:20
Community♦
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
$endgroup$
It is definitely doable without a computer or calculator, with a small computational effort (less than $100$ multiplications modulo $125$)
The numbers of trailing zeros in $2015!$ is equal to the exponent of $5$ in its factorization (since $2$ has a much larger exponent than $5$), which is:
$$lfloor2015/5rfloor+lfloor2015/5^2rfloor+...=403+80+16+3=502$$
If $x=frac{2015!}{5^{502}}$, all the difficulty is to calculate $xbmod 5^3$. If we would know $xbmod 5^3$, then $2^{502}bmod 5^3=4$ (follows easily from Euler's theorem $2^{100} bmod 5^3=1)$, and its inverse modulo $5^3$ (using for example $4cdot 31=-1 bmod 5^3$).
This would give us the value of $frac{2015!}{10^{502}}bmod 5^3$. As we already know that $frac{2015!}{10^{502}}bmod 2^3=0$, the value of $frac{2015!}{10^{502}}bmod 1000$ would follow by the CRT.
To calculate $xbmod 5^3$, we can use Gauss's generalization of Wilson's theorem. This gives $$prod_{substack{i=1\ 5nmid i}}^{5^3} i equiv -1 pmod {5^3}$$
So we can get rid of entire chunks of $125$ elements
We can get rid first of $2001cdot...cdot2015$. This gives $5^3$, and the rest of the factors are congruent to $74$ modulo $5^3$
From $2000!$ we can take out $5^{400}$, the product of the terms which are not divisible by $5$ is $1bmod 5^3$ (Gauss), and we are left with $400!$
From $400!$ we can take out $5^{80}$, Gauss's theorem gives the product of the terms non-divisible by $5$ up to $375$ as being $-1bmod 5^3$, and all that is left is to calculate $376cdot377cdot378cdot379cdot381cdot...cdot399bmod 5^3$. Then we are left with $80!$
From $80!$ we can take out $5^{16}$. For the product $y$ of the terms non-divisible by $5$, we can calculate first $z=81cdot82cdot83cdot84cdot86cdot...cdot124$ and solve $ycdot zequiv -1 pmod {5^3}$
Then $16!$ is manageable.
There may be more shortcuts that I haven't seen, and/or stronger theorems in number theory, but this is how I would have approached this problem, should I have lived a century ago.
edited Jan 2 at 9:20
Community♦
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
edited Jan 2 at 9:20
Community♦
1
edited Jan 2 at 9:20
Community♦
1
edited Jan 2 at 9:20
Community♦
1
1
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
answered Dec 23 '16 at 2:56
MomoMomo
12k21430
12k21430
add a comment |
add a comment |
$begingroup$
The last three non-zero digits are 544 (followed by 502 zeros).
Computed using the online Big Integer Calculator.
Here is a one-line program avoiding large numbers:
m=1;for(k=2,2015,m=m*k;while(m%10==0,m=m/10);m=m%1000);print(m)
(PARI/GP)
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
$endgroup$
add a comment |
$begingroup$
The last three non-zero digits are 544 (followed by 502 zeros).
Computed using the online Big Integer Calculator.
Here is a one-line program avoiding large numbers:
m=1;for(k=2,2015,m=m*k;while(m%10==0,m=m/10);m=m%1000);print(m)
(PARI/GP)
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
$endgroup$
add a comment |
$begingroup$
The last three non-zero digits are 544 (followed by 502 zeros).
Computed using the online Big Integer Calculator.
Here is a one-line program avoiding large numbers:
m=1;for(k=2,2015,m=m*k;while(m%10==0,m=m/10);m=m%1000);print(m)
(PARI/GP)
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
$endgroup$
The last three non-zero digits are 544 (followed by 502 zeros).
Computed using the online Big Integer Calculator.
Here is a one-line program avoiding large numbers:
m=1;for(k=2,2015,m=m*k;while(m%10==0,m=m/10);m=m%1000);print(m)
(PARI/GP)
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
edited Dec 23 '16 at 5:40
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
answered Dec 23 '16 at 5:03
AlexAlex
4,2251628
4,2251628
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%2f2069177%2fwhat-are-the-last-three-non-zero-digits-of-2015%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$
well, i forgot to put non zero
$endgroup$
– Parnaek Siagian
Dec 23 '16 at 3:02
1
$begingroup$
See her for useful hints
$endgroup$
– Shailesh
Dec 23 '16 at 3:08
$begingroup$
See here as well: mathforum.org/library/drmath/view/71768.html
$endgroup$
– Rohan
Dec 23 '16 at 3:26
$begingroup$
The problem of calculating $n! pmod m$ for $n < m$ is known to be very hard (afaik unsolved in polynomial time). This problem is basically asking "solve $n! / q pmod m$ for $n > m$, with $q$ being a sufficiently large factor to prevent the product from devolving to zero". It seems "obvious" (aka I can't prove it but seems provable) that this is a strictly harder problem than the first one I mentioned, so you aren't going to do better than just running a computer program, asymptotically.
$endgroup$
– DanielV
Dec 23 '16 at 8:32