I need an opinion and maybe a clarification about my work on the following problem:

43 Views Asked by At

Problem: Suppose that $m_1,m_2,...,m_t$ are positive integers and $a_1,a_2,...,a_t$ are integers.

What condition on $m_1,m_2,...,m_t$ is necessary to guarantee that there is an integer x such that $x ≡ a_i $ mod $m_i$ for all intergers i in the range $1\leq i\leq r $.

My idea: I will choose for presentation x=1, $a_1=14$ and $m_1=13$.

Now let k be any positive integer. So that $a_n=a_1+k*(n-1)$ where n>0. Similarly let $m_n=m_1+k*(n-1)$.

Now for any n, 1 ≡ $a_n $ mod $m_n$.

The solution is that $m_1,m_2,...,m_t$ is pairwise coprime.

In my presentation if I have k=2 then my m's will not be pairwise coprime.

Could you please explain why the answer is pairwise coprime and why will my idea not work.

1

There are 1 best solutions below

2
On BEST ANSWER

Normally you are given the $a$'s and $m$'s and asked to find $x$. If the $m$'s are pairwise coprime, the Chinese Remainder Theorem guarantees a solution. If they are not, there may not be a solution. As an example, take $m_1=4, m_2=6$, which have common factor $2$. Then if $a_1=1,a_2=2$ there is no solution because the first forces $x$ to be odd and the second forces $x$ to be even.