Algebra I: Cyclic Generators

Question

The direct product $\mathbb{Z}_{45} \times \mathbb{Z}_{98}$ is cyclic and isomorphic to $\mathbb{Z}_{4410}$ because $gcd(45,98)=1$; furthermore the element $n=([1]_{45},[1]_{98})$ is a cyclic generator. Find the smallest positive integer $m$ such that $mn=([29]_{45},[17]_{98})$

Answer 1

You need $m$ such that $m\equiv 29 \mod{45}$ and $m\equiv 17 \mod{98}$.

You have that $m=29+45x$ from the first one and then from the second one you get: $$ 29+45x-17\equiv 0 \mod{98} \Rightarrow 12+45x=98y $$ So you need to solve $12=-45x+98y$ or equivalently $45t+98s=1$ since $gcd(45,98)=1$. From Euclidean algorithm you obtain that $t=98k+61$, $s=-45k-28$ for $k\in\mathbb{Z}$. We need the smallest negative such $t$ so $x$ is the smallest positive that works. For $k=-1$ we get:

$$ t=-37 \quad s=17 $$ So $x=37*12$ hence $m=29+45*37*12=20009$.

Answer 2

Hint: Chinese remainder theorem

Answer 3

m=29mod45 and m=17mod98

so

29+45m=17mod98 and 45m=-12mod98=86mod98

m=52