- #1
geoffrey159
- 535
- 72
Homework Statement
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))##
Homework Equations
Bezout theorem
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) ##