1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Arithmetic homework

  1. May 5, 2015 #1
    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. jcsd
  3. May 6, 2015 #2
    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



Similar Discussions: Arithmetic homework
  1. Modular arithmetic (Replies: 3)

  2. Arithmetics problem (Replies: 5)

  3. Cardinal arithmetic (Replies: 39)

Loading...