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

Re: [PrimeNumbers] Puzzle - Law of small numbers

Expand Messages
  • Phil Carmody
    ... Well, an upper bound is 160470643909878751793805444097921 Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail
    Message 1 of 5 , Jan 10, 2007
    • 0 Attachment
      --- jbrennen <jb@...> wrote:
      > What is the smallest N such that sigma(N) is congruent to
      > 17 (modulo 102)?

      Well, an upper bound is 160470643909878751793805444097921

      Phil



      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    • thefatphil
      Apologies if people get 2 copies - yahoo seems flakey, so I m trying again. ... An upper bound is 160470643909878751793805444097921 Phil
      Message 2 of 5 , Jan 10, 2007
      • 0 Attachment
        Apologies if people get 2 copies - yahoo seems flakey, so I'm trying
        again.

        --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:
        > What is the smallest N such that sigma(N) is congruent to
        > 17 (modulo 102)?

        An upper bound is 160470643909878751793805444097921

        Phil
      • Adam
        I think you can prove that Phil s example 103^16 is the smallest such number. Sigma(n) has factors (1+p+p^2+...+p^k) for p^k||n (
        Message 3 of 5 , Jan 10, 2007
        • 0 Attachment
          I think you can prove that Phil's example 103^16 is the smallest
          such number. Sigma(n) has factors (1+p+p^2+...+p^k) for p^k||n (<-
          largest power of p that divides n). For sigma(n) to be 5 mod 6, all
          the factors have to be either 1 or 5 mod 6 (i.e., no factors that
          are 2,3,4,0 mod 6). By examination, for p=2 and p=3,
          (1+p+p^2+...+p^k) is never 0 mod 17 and 1 or 5 mod 6.

          For p=3, we get 1+3+3^2+...+3^k odd when k is even but then
          1+3+3^2+...+3^k=(3^(k+1)-1)/2 while the order of 3 mod 17 is 16 so 3^
          (k+1)-1 is divisible by 17 only when 16 divides k+1. It can not be
          true that k is even and 16 divides k+1.

          For p=2, we get 1+2+2^2+...+2^k is 1 mod 3 when k is even. But the
          order of 2 mod 17 is 8, so 2^(k+1)-1 == 0 mod 17 means (k+1) is even.

          The only other available primes are either 1 or 5 mod 6. If p is 5
          mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is even. If p
          is 1 mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is either
          4 or 6 mod 6.

          For k even, solve 1+x+...+x^k==0 mod 17 and find the first solution
          happens when k=16 and x==1 mod 17. The first prime that is 1 mod 17
          is 103. 103^16 is the first number that solve sigma(n)==17 mod 102.
        • jbrennen
          ... Yes, and you seemed to give a convincing argument. :) Did anyone notice that I basically gave away the key to finding Phil s example? I stated that
          Message 4 of 5 , Jan 10, 2007
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "Adam" <a_math_guy@...> wrote:
            >
            > I think you can prove that Phil's example 103^16 is the smallest
            > such number.

            Yes, and you seemed to give a convincing argument. :)


            Did anyone notice that I basically gave away the key to finding
            Phil's example? I stated that solving sigma(N) == 5 (mod 6)
            was easily done by picking a prime p of the form 6*x+1 and
            then taking p^4, or p^(5-1).

            This is of course easily generalized...

            So to solve sigma(N) == 17 (mod 102), find a prime of the
            form 102*x+1. The first such is of course 103. And then
            set N = 103^(17-1) = 103^16.



            The tricky part is proving that 103^16 is in fact the minimal
            solution.

            My method for doing so:

            Note that N must be divisible by a prime power p^a which
            has sigma(p^a) divisible by 17 but not divisible by 2 or 3.

            Note also that sigma(p^a) = (p^(a+1)-1)/(p-1).

            In order for sigma(p^a) to be an odd number (not divisible
            by 2), we need to have either p or a be even.

            If p is even, it must be 2, and we would have:
            p^(a+1) == 1 (mod 17). It turns out that this is true
            when a == 7 (mod 8); however, when a == 7 (mod 8), we
            also have sigma(2^a) divisible by 3. So that doesn't
            work.

            So p must be odd and a must be even. In order for
            p^(a+1)-1 (the numerator of the expression above) to
            be divisible by 17, (a+1) must be divisible by the
            order of p modulo 17. Note that the order of p
            modulo 17 must divide evenly into 16 (a consequence
            of Fermat's Little Theorem). So we have an
            odd number (a+1) which must be divisible by a
            divisor of 16. Clearly the divisor (the order of
            p modulo 17) must be 1. This implies that the
            prime p is in fact of the form 17*x+1.

            And once we know that p == 1 (mod 17), we can see
            easily that a must be of the form 17*y-1.

            The smallest prime p of the form 17*x+1 is 103,
            and the smallest exponent a of the form 17*y-1 is 16.

            So the smallest prime power which has sigma(p^a)
            divisible by 17, but not by 2 or 3, is 103^16.

            So any solution N to the original puzzle must be
            divisible by a prime power >= 103^16.



            There are not a lot of ordered pairs (A,B) such
            that A > 2 and such that N = (B+1)^(A-1) is the
            smallest solution to sigma(N) == A (modulo B).

            I know of these three: (5,6), (5,30), and (17,102).

            There could be others, if anyone wants to try
            to find them. It's interesting that for those
            three I know of, A is always a Fermat prime.
          Your message has been successfully submitted and would be delivered to recipients shortly.