1
$\begingroup$

Can x mod (N - a) or x mod (N + a) be calculated just by knowing x mod N? where a is an arbitrary integer, and N is a prime. e.g. i know 22! mod 23 ≡ 22 using Wilson's theorem. lets say i want to know 22! mod 24, is there a way i can do so without solving the factorial?

$\endgroup$
  • $\begingroup$ I added an answer which discusses the general case. $\endgroup$ – Bill Dubuque Jan 8 at 20:21
1
$\begingroup$

If $\,d := \gcd(n,m)=1\,$ then there is no relationship between $\,a = x\bmod n\,$ and $\, b = x\bmod m\,$ since CRT $\,\Rightarrow\,x\equiv a\pmod{\!n},\ x\equiv b\pmod{\! m}\ $ is solvable for all values of $\,a,b.\,$ This is true in your example $\iff 1 = \gcd(n,n\pm a) = \gcd(n,a).$

However, when $\,d > 1\,$a solution exists iff $\,b\equiv a\pmod{\!d},\,$ and this does place constraints on the values $\,b\,$ that $\,x\,$ can take $\!\bmod m$. Then $\,b\,$ is determined uniquely iff $\,m\mid d\iff m\mid n\ $ (i.e. iff $\,n\pm a\mid n\,$ in your example), hence $\,x\bmod m = (x\bmod n)\bmod m\,$ is uniquely determined. This arises frequently, e.g. knowing $\, u = x\bmod 10 = $ units digit of $x$ we can compute its parity by taking the parity of its units digit, i.e. $\ x\bmod 2 = (x\bmod 10)\bmod 2 = u\bmod 2,\,$ e.g. $\,123\bmod 2 = 3\bmod 2 = 1$.

$\endgroup$
1
$\begingroup$

For the specific case $22!$, the answer is easy: since $4 \leq 22$ and $6 \leq 22$ you have that $22! = 0 \pmod{24}$. However, we didn't use the fact we got from Wilson's Theorem, and it doesn't help us in general.

The answer to your question is no, and here is an illustrative example: suppose you know that $x = 5 \pmod{10}$. Then you could have, among many options, that $x = 5$, or that $x = 15$. In the former case, $x = 5 \pmod{12}$. In the latter case, $x = 3 \pmod{12}$.

$\endgroup$
  • $\begingroup$ But the answer can be yes too, e.g. $\,n=10, n−a=5.\ $ See my answer for the general case. $\endgroup$ – Bill Dubuque Jan 8 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.