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

RE: [PrimeNumbers] reduced residue systems question please help

Expand Messages
  • 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 1 of 5 , Mar 1 1:29 AM
    • 0 Attachment
      --- 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 2 of 5 , Mar 1 3:29 AM
      • 0 Attachment
        '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 3 of 5 , Mar 1 1:20 PM
        • 0 Attachment
          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.