10
$\begingroup$

Honestly, I have no idea how to proceed in this. I tried to combine both divisibilities critirea of $3$ and $7$, and tried to get a general form for a number being a multiple of $3$ and $7$, but I couldn't get any (and I wasn't hopeful).

If anyone could help me, I would be grateful!

$\endgroup$
  • 7
    $\begingroup$ $x \equiv 0 \pmod {21}, \; \; $ $x \equiv 241 \pmod {1000}$ $\endgroup$ – Will Jagy Nov 26 '17 at 0:22
  • 4
    $\begingroup$ Notice that $\mbox{gcd}(1000,21) =1$ and use chinese remainder theorem. It guarantees that the system of linear congruences given by @WillJagy has a unique solution modulo $N = 21\times 1000$ $\endgroup$ – math.h Nov 26 '17 at 0:33
  • 1
    $\begingroup$ You want to find whole number solutions of $21x = 1000y + 241$. Do you know how to find all the whole number solutions of $21x - 1000y = 1$? $\endgroup$ – PM 2Ring Nov 26 '17 at 1:24
  • 1
    $\begingroup$ If you have one $x, y$ pair that's a solution to $21x = 1000y + 241$ then we can also say $21(x + 1000k) = 1000(y + 21k) + 241$ for any $k$. $\endgroup$ – PM 2Ring Nov 26 '17 at 3:03
  • $\begingroup$ @Robson: Please stop making limits in titles taller by using the \limits switch. The goal is to make titles as short as possible. That kind of edit is great in the body, where I agree it's more readable. But if you make the title taller, it takes up too much space in the Questions list. It's frowned on here at M.SE. $\endgroup$ – Adrian Keister Oct 6 '18 at 19:56
9
$\begingroup$

Basically you have $$x=21a\\x=1000b+241$$ where $a,b,x\in\mathbb N$. It is true for $x=17241,a=821,b=17$.

As I know, there is no known method to obtain all possible solutions if you, in general, replace $21$ and $1000$ with some arbitrary numbers. However, according to the Chinese Remainer Theorem, if the greatest common divisor of the two given numbers is $1$, it then has unique solution modulo $a\cdot b$ (where $a$ and $b$ are the given numbers), as math.h explained in the comment. Therefore, finding one example basically solves the problem.

$\endgroup$
  • 3
    $\begingroup$ I don't feel like this really answers the question asked. It gives one example, but doesn't describe the general case or describe how this answer was obtained. $\endgroup$ – Milo Brandt Nov 26 '17 at 0:59
  • 2
    $\begingroup$ @MiloBrandt. As I know, there is no known method to obtain all possible solutions if you, in general, replace $21$ and $1000$ with some arbitrary numbers. However, according to the CRT, if the greatest common divisor of the two given numbers is $1$, it then has unique solution modulo $a\cdot b$ (where $a$ and $b$ are the given numbers), as math.h explained in the comment. Therefore, finding one example basically solves the problem. $\endgroup$ – user499203 Nov 26 '17 at 1:03
  • 3
    $\begingroup$ That comment would make a nice addition to the answer, I think - I meant that the answer didn't mention that periodicity. (Though, to be sure, there is a way to use the CRT constructively in the general case, so long as you're willing to compute multiplicative inverses mod $a$ and $b$ - which may be done with the Euclidean algorithm) $\endgroup$ – Milo Brandt Nov 26 '17 at 1:35
  • 2
    $\begingroup$ @MiloBrandt. Ok, I included the comment in the post. $\endgroup$ – user499203 Nov 26 '17 at 5:23
10
$\begingroup$

In your shoes, I would have tried Wolfram Alpha. Something like solve 21x = 241 mod 1000 should give you the answer:

$x = 821 + 1000n$ and $n \in \mathbb Z$

Well, that needs to be qualified with $n \geq 0$, since negative $n$ give numbers like $-3759$. Positive $n$, and 0, will give you the numbers you want: 17241, 59241, 80241, etc.

Also observe that the last three digits of multiples of 21 cycle at every thousand, which is a bit longer than, say, multiples of 22 (which cycle the last three digits every five hundred multiples).

$\endgroup$

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.