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

hi everyone.

Expand Messages
  • omidmazaheri
    Hi Every one. I need to solve this problem.please help me. Prove that for each prime number (that is not 2 or 5) and each natural number N ,there is a power of
    Message 1 of 4 , Apr 30, 2002
    • 0 Attachment
      Hi Every one.
      I need to solve this problem.please help me.

      Prove that for each prime number (that is not 2 or 5) and each
      natural number N ,there is a power of P that ends with 000...001,
      where the number of zeroes is N-1
    • Phil Carmody
      ... Look at the finite fields F_(2^N) and F_(5^N). What are the orders, of the element p in the multiplicative groups of this field? Call these orders o5 and
      Message 2 of 4 , May 1 1:47 AM
      • 0 Attachment
        --- omidmazaheri <omidmazaheri@...> wrote:
        > Hi Every one.
        > I need to solve this problem.please help me.
        >
        > Prove that for each prime number (that is not 2 or 5) and each
        > natural number N ,there is a power of P that ends with 000...001,
        > where the number of zeroes is N-1

        Look at the finite fields F_(2^N) and F_(5^N). What are the orders,
        of the element p in the multiplicative groups of this field?
        Call these orders o5 and o2. What is p^lcm(o2,o5) in this field?

        Phil


        __________________________________________________
        Do You Yahoo!?
        Yahoo! Health - your guide to health and wellness
        http://health.yahoo.com
      • aditsu
        ... Wow, I solved this problem at a national maths contest when I was about 13 y.o. My solution was something like this (it actually works for every odd number
        Message 3 of 4 , May 1 8:39 AM
        • 0 Attachment
          --- "omidmazaheri" wrote:
          > Hi Every one.
          > I need to solve this problem.please help me.
          >
          > Prove that for each prime number (that is not 2 or 5) and each
          > natural number N ,there is a power of P that ends with 000...001,
          > where the number of zeroes is N-1

          Wow, I solved this problem at a national maths contest when I was
          about 13 y.o. My solution was something like this (it actually works
          for every odd number that doesn't end in 5):

          step 1) each number P of this kind ends in 1, 3, 7 or 9; then P^4
          obviously ends in 1, let q=P^4

          step 2) if q=r*10^s+1 (s>0) then q^2=2*t*10^s+1
          proof: q=r*10^s+1 => q^2=2*(r^2*5*10^(s-1)+r)*10^s+1
          let u=q^2

          step 3) if u=2*t*10^s+1 then u^5=v*10^(s+1)+1
          proof: let w=2*t*10^s; u=w+1 => u^5=w^5+5*w^4+10*w^3+10*w^2+5*w+1;
          we note that w^2 and 5*w are divisible with 10^(s+1), therefore we
          can write u^5=v*10^(s+1)+1 (v is integer)

          step 4) from 2) and 3) we have: q=r*10^s+1 => q^10=v*10^(s+1)+1;
          through induction we can prove that q^(10^N)=r_N*10^(s+N)+1 (where
          r_N are integers) for every N>=0

          step 5) replacing q=P^4 and s=1 we get P^(4*10^N)=r_N*10^(N+1)+1, so
          P^(4*10^N) ends in N zeroes followed by an 1


          final note: this is probably not the shortest solution, but it's an
          elementary one

          Adi
        • Phil Carmody
          ... Just Phil , no need for Mr. :-) ... Nope, I mean the finite field with p^N elements, where in this case p=2 and p=5. The statement, seen a few posts
          Message 4 of 4 , May 1 10:16 AM
          • 0 Attachment
            --- "S.R.Sudarshan Iyengar" <gayathrisr@...> wrote:
            > >> Prove that for each prime number (that is not 2 or 5) and each
            > >> natural number N ,there is a power of P that ends with
            > 000...001,
            > >> where the number of zeroes is N-1
            >
            > >Look at the finite fields F_(2^N) and F_(5^N). What are the
            > orders,
            > >of the element p in the multiplicative groups of this field?
            > >Call these orders o5 and o2. What is p^lcm(o2,o5) in this field?

            > Well Mr. Phil

            Just 'Phil', no need for 'Mr.' :-)

            > what do you mean by F_(2^N) do you mean that it is
            > the field
            > containing all elements >=1 which are relatively prime to 2^N?

            Nope, I mean the finite field with p^N elements, where in this case
            p=2 and p=5.

            The statement, seen a few posts back, that p \in {1,3,7,9} (mod 10)
            implies p^4 == 1 (mod 10) is a statement that Order(p) divides 4 for
            such p in (Z/10Z)* . The statement that if q == 1 (mod p^n), then
            q^10 == 1 (mod p^(n+1)) for p=2,5 effectively says that the order of
            q in F_(2^(n+1)) divides 10 times the order of q in F_(2^n).

            I think my hints get to the root of the problem, but the
            demonstrative proof we saw was probably simpler as it didn't care
            what the order actually was, it didn't matter - as long as you raise
            a number by a multiple of its order you get the result you need.
            (e.g. raising 10n+1 to the power 4 in order to get a number of the
            form 10n+1 is a tad unnecessary, but it works.)


            Phil

            __________________________________________________
            Do You Yahoo!?
            Yahoo! Health - your guide to health and wellness
            http://health.yahoo.com
          Your message has been successfully submitted and would be delivered to recipients shortly.