Modular Arithmetic - Solve $a$ and $b$ given equation for $x$

44 Views Asked by At

This is an application to the Chinese Remainder Theorem.
Given $x=63k+12\ \ \forall k\in\mathbb{Z}$, solve for $a$ and $b$ that satisfy the relation $$x\equiv a \mod7 \\ x\equiv b \mod 9$$

So far these are my attempts:
Since $$\begin{align} x&=a+7i\\ &=a+7(7^{-1}\otimes_{9}(b-a)+9r)\\ &=a+7*(4\otimes(b-a))+63r \end{align}$$ Now the problem becomes $a+7*(4\otimes(b-a))=12$.
How could I proceed? Thank you.


EDIT:
Thanks to everyone who contributed. Head is stumped after a day of study...

1

There are 1 best solutions below

1
On

That is simple, divide 63k +12 by 7 and the remainder you get is 5 since 63k divisible by 7 but 12 leaves a remainder of 5. Thus by definition if we proceed similarly for 9 and that 12 leaves a remainder 3. Hence a=7t+5 and b=9t+3 ;t is an integer.