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

Re: Puzzle - Law of small numbers

Expand Messages
  • 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 1 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.