$x\equiv 6\pmod {13}$

$x\equiv 0\pmod {43}$

$x\equiv 10^n \pmod {41}$.

For x and n nonnegative integers.

Using Wolphram I found a set of solutions:

$x=903+22919\cdot s$ is one solution

Another is:

$14319+22919\cdot s$

let’s call the generic solution:

$d+22919\cdot s=x$, with d an integer depending on n.

How can I prove that d is either $\equiv 0\pmod {215}$ or $\equiv 129\pmod {215}$ or in only one case $\equiv 43\pmod{215}$? Or is the statement false?

  • $\begingroup$ @Dietrich Burde not x but d $\endgroup$ – gondoliere Jan 25 at 9:36
  • 2
    $\begingroup$ You probably want to look at en.wikipedia.org/wiki/Chinese_remainder_theorem, especially the section about "Computation" which contains an example. This should be enough for you to start by adapting the proof to your case ! $\endgroup$ – Numbra Jan 25 at 9:39
  • $\begingroup$ You found the solutions of the CRT system for $\,n=0,1.\,$ You also need to find the solutions for $\,n=2,3,4\,$ since $\,10\,$ has order $5$ modulo $41$. You will find that they are not all of the form you presume. Why did you presume that form? Why are you working modulo $\,215?\ \ $ $\endgroup$ – Bill Dubuque Jan 25 at 18:42

If you first check the possibilities for $x\equiv 10^n \pmod {41}$ you will find that $x$ is congruent to one of $1,10,16,18,37$ modulo $41$.

You can now apply the Chinese Remainder Theorem to see that you require numbers of the form $43d+22919s$, where $43d\equiv 6 \pmod {13}$ and $43d\equiv 1,10,16,18,37 \pmod {41}$.

These conditions simplify to $d\equiv 8 \pmod {13}$ and $d\equiv 5,8,9,21,39 \pmod {41}$.

It should be straightforward now but ask if anything is unclear! The following answers should allow you to check if you have the right idea. These are the values for the $d$ in your post.



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.