0

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$?

blub
  • 4,794
Peter Sanchez
  • 1
  • 6
    If you just want a single $x$ that works, you could set $x=23\cdot60\cdot 60\cdot 1000-1195$. – hmakholm left over Monica Aug 21 '18 at 23:18
  • If $a,b$ are given, then $a \equiv b \mod x$ if and only if $x$ divides into $a-b$. – Ian Aug 21 '18 at 23:21
  • @Ian: We might require that $x \gt b$ so you need a large enough factor of $a-b$. It depends whether you require that $b$ be less than the modulus. – Ross Millikan Aug 21 '18 at 23:25
  • @RossMillikan Yeah, I arguably rephrased the question by posing it in terms of $a \equiv b \mod x$; if we interpret this in terms of a modulus operator then you indeed need $x>b$ as well. – Ian Aug 21 '18 at 23:26
  • For $a \equiv b \mod x$ and and you want $a> x > b$ doing $x = a - b$ is pretty simple. I you want a smaller $x> 1195$ we can see that $5|1195$ so $5|2360601000 - 1195$ and $\frac {2360601000-1195}5$ is certainly bigger than $1195$, As $2,3,23$ don't divide $1195$ they don't divide $2360601000-1195$ so finding another factor $> 1195$ may or may not be possible. $\frac{2360601000-1195}{1195}\approx 69287$ so if there is any factor larger than 5 but less than 69287 we can divide by that and that will be an appropriate $x$. – fleablood Aug 22 '18 at 00:30

2 Answers2

2

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$.

hmakholm left over Monica
  • 286,031
0

$(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$.

fleablood
  • 124,253