# How to prove this set of congruences involving various moduli?

Consider:

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

• @Dietrich Burde not x but d – gondoliere Jan 25 at 9:36
• 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 ! – Numbra Jan 25 at 9:39
• 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?\ \$ – 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.
$$344,903,10965,14319,17114.$$