0
$\begingroup$

I am learning about the Chinese remainder theorem, and am having trouble understanding a part of it. I am. sure that something about that way I understand it is flawed, but I don't know what. This is probably a stupid question, so I am sorry. But here goes.

Say I am trying to find some $x \equiv 1 \pmod{14^k}$. Does the Chinese remainder theorem say that this requires $x \equiv 1 \pmod{7^k}$ and $x \equiv 1 \pmod{2^k}$? This is clearly not possible, because it would have to be even and odd at the same time. I have tried to clear up this misunderstanding by looking around the internet, but I don't seem to understand the theorem properly and this is what I keep coming back to. What does the theorem really say about what $x$ should be equal to mod $7^k$ and $2^k$?

$\endgroup$
4
  • 1
    $\begingroup$ The chinese remainder theorem means basically the other direction of your claim, but your implication is also true, but just follows from $$7^k\mid 14^k\mid x-1$$ and $$2^k\mid 14^k\mid x-1$$ Additionally $$x\equiv 1 \mod 7^k$$ does not imply that $\ x\ $ is even. $\endgroup$
    – Peter
    Mar 12, 2020 at 16:37
  • $\begingroup$ The chinese remainder theorem states : If $m_1,\cdots ,m_k\ge 2$ are pairwise coprime integers then for every tuple $(a_1,\cdots , a_k)$ there is an integer $x$ uniquely modulo $m_1\cdot m_2\cdots m_k$ with $x\equiv a_j\mod m_j$ for $j=1,\cdots,k$ $\endgroup$
    – Peter
    Mar 12, 2020 at 16:42
  • $\begingroup$ E.g., $15$ is odd and $15\equiv1\pmod7$ and $15\equiv1\pmod2$ (and the same is true for $1$ in place of $15$) $\endgroup$
    – J. W. Tanner
    Mar 12, 2020 at 17:02
  • $\begingroup$ Why are you using CRT here? By definition $\,x\equiv 1\pmod{\!14^k}\iff x = 1 + 14^k n\,$ for some integer $n.\ $ There is nothing to "find" without any further constraints on $x\ \ $ $\endgroup$
    – Bill Dubuque
    Mar 12, 2020 at 17:29

3 Answers 3

Reset to default
1
$\begingroup$

This is clearly not possible, because it would have to be even and odd at the same time.

This seems to be the origin of your confusion. In fact, $x$ does not need to be even: the fact that $x \equiv 1 \pmod{7^k}$ means that there is an integer $m$ such that $x = 1 + m7^k$. When $m$ is even, clearly $x$ is odd. In fact, you can take $m = 2^k$, and this gives you the (a) correct $x$.

$\endgroup$
0
$\begingroup$

$1$ is odd, $1 \pm 7^k$ are even, $1 \pm 2\cdot 7^k$ are odd, et c. So it is not the case that the congruence class containing $1$ modulo $7^k$ only contains even numbers. The congruence class containing $1$ modulo $2^k$ does only contain odd numbers, so a compatible choice modulo $7^k$ must be $1 \pm (2m)7^k$ for some integer $m$.

$\endgroup$
0
$\begingroup$

ANSWER

Well I think your misconception is here.

This is clearly not possible, because it would have to be even and odd at the same time.

The thing is that you are mistaking the congruence with equality. Which means, in stead of $x^k-1 \equiv 0 \pmod{7^k}$ you are taking $x^k -1 = 7^k$.

Let's look at $k=1$, now it is clear that $x=15$, so $x$ can be odd without interfering with the 7 modular.

NOTES

A common strategy upon looking for a root of a CRT system modular $m$ and $m'$ is to call out a reciprocal modular $m'$ of $m$ and vice versa.

Thus, basically CRT is still true.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .