Loading ...
Sorry, an error occurred while loading the content.
 

reduced residue systems question please help

Expand Messages
  • velozant <velozant@msu.edu>
    I was looking at http://www.primepuzzles.net/problems/prob_037.htm and in the proof of the formula mr Fengsui claims that ...the class of residues Tn mod mn
    Message 1 of 5 , Feb 28, 2003
      I was looking at

      http://www.primepuzzles.net/problems/prob_037.htm

      and in the proof of the formula mr Fengsui claims that
      "...the class of residues Tn mod mn is equivalent to the class of
      residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"

      could anyone explain to me in simple terms why this is?

      any help will be greatly appreciated. have a good day.
    • Jon Perry
      Suppose that: the Tn is a complete set of residues prime to mn, the least number more than 1 in this set U(Tn) is the n-th prime pn. The number of elements of
      Message 2 of 5 , Feb 28, 2003
        'Suppose that: the Tn is a complete set of residues prime to mn, the least
        number more than 1 in this set U(Tn) is the n-th prime pn. The number of
        elements of the set Tn is | Tn |=(p1-1)*(P2-1)*...*(p[n-1]-1). If p>p[n-1]
        is a prime, then p belongs the class of residues Tn mod mn.'

        I don't get this. mn is defined as "Let mn=p0*p1*...p[n-1]", therefore
        m2=2.3=6 and m3=2.3.5=30

        However, the number of residues prime to 30 is
        |{2,3,5,7,11,13,17,19,23,29}|=10, and not the 8 predicted by Liu. I suppose
        the p>3 property comes into play...

        'If p>p[n-1] is a prime, then p belongs the class of residues Tn mod mn.'

        Suppose p is a prime and p doesn't belong to tmod30, this is impossible.
        Induction carries on from here.

        I think what '"...the class of residues Tn mod mn is equivalent to the class
        of
        residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"'

        means is that we are looking at either (pn,mn)=1 OR (tn+pn,mn)=1.

        HTH

        Jon Perry
        perry@...
        http://www.users.globalnet.co.uk/~perry/maths/
        http://www.users.globalnet.co.uk/~perry/DIVMenu/
        BrainBench MVP for HTML and JavaScript
        http://www.brainbench.com

        -----Original Message-----
        From: velozant <velozant@...> [mailto:velozant@...]
        Sent: 28 February 2003 22:15
        To: primenumbers@yahoogroups.com
        Subject: [PrimeNumbers] reduced residue systems question please help


        I was looking at

        http://www.primepuzzles.net/problems/prob_037.htm

        and in the proof of the formula mr Fengsui claims that
        "...the class of residues Tn mod mn is equivalent to the class of
        residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"

        could anyone explain to me in simple terms why this is?

        any help will be greatly appreciated. have a good day.


        Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        The Prime Pages : http://www.primepages.org/



        Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      • Phil Carmody
        ... Woh! Steady on, Jon. You re _way_ off base here. 2 is not coprime to 30. gcd(2,30)=2 3 is not coprime to 30. gcd(3,30)=3 5 is not coprime to 30.
        Message 3 of 5 , Mar 1, 2003
          --- Jon Perry <perry@...> wrote:
          > 'Suppose that: the Tn is a complete set of residues prime to mn, the least
          > number more than 1 in this set U(Tn) is the n-th prime pn. The number of
          > elements of the set Tn is | Tn |=(p1-1)*(P2-1)*...*(p[n-1]-1). If p>p[n-1]
          > is a prime, then p belongs the class of residues Tn mod mn.'
          >
          > I don't get this. mn is defined as "Let mn=p0*p1*...p[n-1]", therefore
          > m2=2.3=6 and m3=2.3.5=30
          >
          > However, the number of residues prime to 30 is
          > |{2,3,5,7,11,13,17,19,23,29}|=10, and not the 8 predicted by Liu. I suppose
          > the p>3 property comes into play...

          Woh! Steady on, Jon. You're _way_ off base here.

          2 is not coprime to 30. gcd(2,30)=2
          3 is not coprime to 30. gcd(3,30)=3
          5 is not coprime to 30. gcd(5,30)=5

          1 is coprime to 30. gcd(1,30)=1

          |{1,7,11,13,17,19,23,29}| = 8 as correctly stated by Liu.

          And Liu was not "predicting", this isn't reading chicken entrails, it's a
          simple mathematical fact.


          Phil


          =====
          "Only an admission that he does possess weapons of mass destruction
          would do, sources said: 'The rest is just gesture politics." -- Hoon

          "Are you still bombing your wife?" -- Winjer

          __________________________________________________
          Do you Yahoo!?
          Yahoo! Tax Center - forms, calculators, tips, more
          http://taxes.yahoo.com/
        • Jon Perry
          Woh! Steady on, Jon. You re _way_ off base here. 2 is not coprime to 30. gcd(2,30)=2 3 is not coprime to 30. gcd(3,30)=3 5 is not coprime to 30. gcd(5,30)=5 1
          Message 4 of 5 , Mar 1, 2003
            'Woh! Steady on, Jon. You're _way_ off base here.

            2 is not coprime to 30. gcd(2,30)=2
            3 is not coprime to 30. gcd(3,30)=3
            5 is not coprime to 30. gcd(5,30)=5

            1 is coprime to 30. gcd(1,30)=1

            |{1,7,11,13,17,19,23,29}| = 8 as correctly stated by Liu.'

            Correct. As the whole page in question
            (http://www.primepuzzles.net/problems/prob_037.htm) is completely littered
            with typos and misleading nomenclature, I don't feel completely aggrieved at
            having made such a simple error.

            As to what 'Tn mod mn is equivalent to the class of residues
            Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1]'

            means, it should read:

            T_n mod m_n is equivalent to the class of residues
            Tn+(<0,1,2,...,pn-1>*<mn>) mod m_(n+1)

            which comes clear if you look at the examples, except for m_n is incorrectly
            defined.

            Jon Perry
            perry@...
            http://www.users.globalnet.co.uk/~perry/maths/
            http://www.users.globalnet.co.uk/~perry/DIVMenu/
            BrainBench MVP for HTML and JavaScript
            http://www.brainbench.com
          • velozant <velozant@msu.edu>
            Thanks a lot for your responses. What I am confused about is that I don t understand how adding * to Tn makes it equivalent mod m[n+1].
            Message 5 of 5 , Mar 1, 2003
              Thanks a lot for your responses. What I am confused about is that I
              don't understand how adding <0,1,2,...,pn-1>*<mn> to Tn makes it
              equivalent mod m[n+1]. What I would like is a theorem like the one
              that one can uset to prove that if (k,S)=1 and S is a reduced
              residue system then so is k*S. I think it should be obvious since
              most people accept it and I see from examples that it is true, but I
              just want to know what theorem he is using to imply this equivalence
              or if it follows directly from the definition of Tn. Any help will
              be greatly appreciated.
            Your message has been successfully submitted and would be delivered to recipients shortly.