# Arithmetic homework

1. May 5, 2015

### geoffrey159

1. The problem statement, all variables and given/known data
We are given $a_1,...,a_n$ in $\mathbb{N}^\star$, all mutually prime, and $a = a_1 \times ... \times a_n$.

Show that for all $(b_1,...,b_n)\in\mathbb{Z}^n$, there is $\beta \in \mathbb{Z}$ such that for all $x \in \mathbb{Z}$ :

$(\forall i = 1 ... n, \ x \equiv b_i (\text{mod } a_i) ) \iff (x\equiv \beta \ (\text{mod } a))$

2. Relevant equations
Bezout theorem

3. The attempt at a solution

Please could you tell me if this is correct ? Thanks !

The idea is that for all $i = 1... n$, $a_i$ and $a/a_i$ are mutually prime, so that there are $(u_i,v_i)\in \mathbb{Z}^2$ such that $1 = a_i u_i + \frac{a}{a_i} v_i$. I can now write $b_i = a_i b_i u_i + \frac{a}{a_i} b_i v_i$

($\Rightarrow$) :
We have : $a_i | ( x - b_i) \Rightarrow a_i | (x - a_i b_i u_i - \frac{a}{a_i} b_i v_i ) \Rightarrow a_i | (x - \frac{a}{a_i} b_i v_i)$.
Also, for $i\neq j$, we have that $a_i | \frac{a}{a_j} b_j v_j \Rightarrow a_i | \sum_{j\neq i} \frac{a}{a_j} b_j v_j$

Setting $\beta = \sum_{ j} \frac{a}{a_j} b_j v_j$, we have that $a_i | (x - \beta)$. Since the $a_i$ are mutually prime, $a| (x-\beta)$

($\Leftarrow$) :
$a$ is the least common multiple of $(a_1,...,a_n)$ (because they are mutually prime).
So for all $i = 1...n$, $a_i | (x-\beta)$.
Also, reusing the fact that $a_i | \sum_{j\neq i} \frac{a}{a_j} b_j v_j$, we have that $a_i | (x - \frac{a}{a_i} b_i v_i) = x - b_i + a_i b_i u_i$.
Therefore $a_i | ( x - b_i)$

2. May 6, 2015

### geoffrey159

The second part of the question is :
' Show that $\mathbb{Z}/a\mathbb{Z}$ and $\mathbb{Z}/a_1\mathbb{Z} \times ... \times \mathbb{Z}/a_n\mathbb{Z}$ are isomorphic. Use $f(\text{cl}_a(x)) = (\text{cl}_{a_1}(x),...\text{cl}_{a_n}(x))$ '

where $\text{cl}_u(x) = \{ y\in \mathbb{Z} , u | y-x \}$

$\bullet$ Injectivity of $f$:
$f(\text{cl}_a(x)) = f(\text{cl}_a(x')) \Rightarrow \forall i = 1...n \ \text{cl}_{a_i}(x) = \text{cl}_{a_i}(x') \Rightarrow \forall i = 1...n \ a_i | x-x'$.
Since the $a_i$ are mutually prime, $a | x - x'$ and therefore $\text{cl}_a(x) = \text{cl}_a(x')$

$\bullet$ Surjectivity of $f$:
Let $y_i \in \mathbb{Z}/a_i\mathbb{Z}$, for all $i = 1...n$. There are $x_i,...,x_n \in \mathbb{Z}$ such that $y_i = \text{cl}_{a_i}(x_i)$.
We are looking for $x$ such that for all $i = 1...n$, $\text{cl}_{a_i}(x_i) = \text{cl}_{a_i}(x)$. So we must find $x$ that solves $a_i | x - x_i$ for all $i = 1...n$. According to question 1, it happens if and only if $a | x - \beta$. So $x = \beta$ works and $f(\text{cl}_a(\beta)) = (\text{cl}_{a_1}(x_1),...\text{cl}_{a_n}(x_n)) = (y_1,...,y_n)$

$\bullet$ $f$ is a morphism from the group $(\mathbb{Z}/a\mathbb{Z},+)$ to $(\mathbb{Z}/a_1\mathbb{Z} \times ... \times \mathbb{Z}/a_n\mathbb{Z},+)$, we just need to use the fact that $\text{cl}_u(x) + \text{cl}_u(x') = \text{cl}_u(x+x')$

Are you ok with that ?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted