Results 1 to 7 of 7

Math Help - modular equations

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    modular equations

    1. Let  n and  a be positive integers and let  d = \gcd(a,n) . Show that the equation  ax = 1\ \text{mod} \ n has a solution if and only if  d = 1 .

    Proof.  (\Rightarrow) Suppose  ax = 1\ \text{mod} \ n has a solution. Then  ax-1 = nk for some  k \in \mathbb{Z} . So  x = (nk+1)/a . From here it follows that  a and  n are coprime?  (\Leftarrow) Suppose  d=1 . Then  a and  n are coprime. So  ax = 0\ \text{mod} \ n has no solutions. Hence  ax = 1\ \text{mod} \ n has a solution.  \square

    2. Let  n be a fixed positive integer greater than  1 . For any integers  i and  j , prove that  i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n .

    Proof. So  i = nq+r and  j = nq'+r' where  r \leq q and  r' \leq q' . Then  i+j = n(q+q') + (r+r') .  \square

    Are these somewhat correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Sampras View Post
    1. Let  n and  a be positive integers and let  d = \gcd(a,n) . Show that the equation  ax = 1\ \text{mod} \ n has a solution if and only if  d = 1 .

    Proof.  (\Rightarrow) Suppose  ax = 1\ \text{mod} \ n has a solution. Then  ax-1 = nk for some  k \in \mathbb{Z} . So  x = (nk+1)/a . From here it follows that  a and  n are coprime?  (\Leftarrow) Suppose  d=1 . Then  a and  n are coprime. So  ax = 0\ \text{mod} \ n has no solutions. Hence  ax = 1\ \text{mod} \ n has a solution.  \square

    2. Let  n be a fixed positive integer greater than  1 . For any integers  i and  j , prove that  i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n .

    Proof. So  i = nq+r and  j = nq'+r' where  r \leq q and  r' \leq q' . Then  i+j = n(q+q') + (r+r') .  \square

    Are these somewhat correct?
    Up to here is awsome

     (\Rightarrow) Suppose  ax = 1\ \text{mod} \ n has a solution. Then  ax-1 = nk for some  k \in \mathbb{Z} .
    but from here we can't really divide by a in \mathbb{Z}

    but we do have  ax-1 = nk \iff ax+(-k)n=1 this tells us that gcd(a,n)=1 becuase we have expressed 1 as a linear combination of a and n.

    (\Leftarrow) Suppose  d=1 . Then  a and  n are coprime. So  ax = 0\ \text{mod} \ n has no solutions. Hence  ax = 1\ \text{mod} \ n has a solution.  \square
    ummm not quite first x=0 is a solution

    Then by the Euclidean algorithm there exists \alpha,\beta \in \mathbb{Z} such that \alpha a +\beta n =1

    use this to show that there does exists a solution.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Sampras View Post
    1. Let  n and  a be positive integers and let  d = \gcd(a,n) . Show that the equation  ax = 1\ \text{mod} \ n has a solution if and only if  d = 1 .

    Proof.  (\Rightarrow) Suppose  ax = 1\ \text{mod} \ n has a solution. Then  ax-1 = nk for some  k \in \mathbb{Z} . So  x = (nk+1)/a . From here it follows that  a and  n are coprime?  (\Leftarrow) Suppose  d=1 . Then  a and  n are coprime. So  ax = 0\ \text{mod} \ n has no solutions. Hence  ax = 1\ \text{mod} \ n has a solution.  \square
    Use the fact that \gcd(a,n)=1 if and only if there exist integers r,s with ra+sn=1. Thus

    ax\equiv1\,(\bmod\,n) has solution in x

    \iff\ ax+kn\,=\,1 for some integer k

    \iff\ \gcd(a,n)\,=\,1

    Quote Originally Posted by Sampras View Post
    2. Let  n be a fixed positive integer greater than  1 . For any integers  i and  j , prove that  i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n .

    Proof. So  i = nq+r and  j = nq'+r' where  r \leq q and  r' \leq q' . Then  i+j = n(q+q') + (r+r') .  \square

    Are these somewhat correct?
    What you want to prove is that if r\equiv i\,(\bmod\,n) and r'\equiv j\,(\bmod\,n) then r+r'\equiv i+j\,(\bmod\,n). Your proof is essentially correct, but it might be better to write the r and r' on the left-hand side instead. (NB: There is no need to assume r\le q or r'\le q'.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by TheAbstractionist View Post
    Use the fact that \gcd(a,n)=1 if and only if there exist integers r,s with ra+sn=1. Thus
    ax\equiv1\,(\bmod\,n) has solution in x
    \iff\ ax+kn\,=\,1 for some integer k

    \iff\ \gcd(a,n)\,=\,1


    What you want to prove is that if r\equiv i\,(\bmod\,n) and r'\equiv j\,(\bmod\,n) then r+r'\equiv i+j\,(\bmod\,n). Your proof is essentially correct, but it might be better to write the r and r' on the left-hand side instead. (NB: There is no need to assume r\le q or r'\le q'.)
    That's only for Euclidean algorithm?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Sampras View Post
    That's only for Euclidean algorithm?
    There is no need to use the Euclidean algorithm for this problem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by TheAbstractionist View Post
    There is no need to use the Euclidean algorithm for this problem.
    But you assume  r \leq q and  r' \leq q' only if you were to use the Euclidean algorithm?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    No,  r, r' < n , but it doesn't really matter for this proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular equations?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 1st 2012, 05:08 PM
  2. Set of 4 simultaneous equations using modular
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: March 18th 2011, 06:53 AM
  3. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 03:40 PM
  4. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2009, 11:16 AM
  5. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 5th 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum