How to solve for $x$: $[ (23 * 60 * 60 *1000)\mod x = 1195 ]?$

Question

I want to solve

$$(23 * 60 * 60 *1000)\mod x = 1195$$

for $x$.

I understand there might be multiple solutions. I have tried plugging it into Wolfram Alpha and I get no output for $x$. How might I solve for $x$?

Answer 1

You want an $x$ such that $82\,800\,000 \bmod x = 1195$, which is to say that $x>1195$ and that $$ 82\,800\,000 = kx+1195 $$ for some integer $k$. Rearranging, this is the same as $$ kx = 82\,798\,805 $$ So what you are looking for is exactly divisors of $82\,798\,805$ that are larger than $1195$.

If you just need one of them, taking $x=82\,798\,805$ is quick and simple.

If you want all of them, you need the prime factorization of $82\,798\,805$. Prime factorizations are not easy in general, but for numbers as small as this we can look them up on the web. It turns out that $$ 82\,798\,805 = 5 · 16\,559\,761 $$ and both of these factors are prime. So there are only four divisors of $82\,798\,805$, namely $$1,\, 5,\, 16\,559\,761,\, 82\,798\,805$$ The two first of these are too small, so $x$ must be either $16\,559\,761$ or $82\,798\,805$.

Answer 2

$(23 * 60 * 60 *1000)\mod x = 1195$ can be rewritten as

$(23*60*60*1000) \equiv 1195 \mod x$ so

$(23*60*60*1000) - 1195 \equiv 0 \mod x$.

So $x$ can be any number that divides $23*60*60*1000-1195$. In particular $x$ can be $23*60*60*1000 - 1195$.