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

Re: [PrimeNumbers] Mersennes mod 14 question

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... Since 14 is composite, the first obvious step is to split it to 2*7, consider the separate cases, and reconstruct using the Chinese Remainder Theorem in
    Message 1 of 4 , Feb 20, 2005
    • 0 Attachment
      On Sunday 20 February 2005 20:57, you wrote:
      > Hi,
      >
      > I noticed that sequential Mersenne numbers seem to progress in the
      > sequence of 1,3,7 mod 14.
      >
      > Does anyone know if the sequence ever breaks down or can it be shown
      > that it continues forever.
      >
      > As an example of what I mean:
      >
      > 2^1-1 = 1 mod 14
      > 2^2-1 = 3 mod 14
      > 2^3-1 = 7 mod 14
      > 2^4-1 = 1 mod 14
      > 2^5-1 = 3 mod 14
      > 2^6-1 = 7 mod 14
      > 2^7-1 = 1 mod 14
      > 2^8-1 = 3 mod 14
      > 2^9-1 = 7 mod 14
      > 2^10-1 = 1 mod 14
      > 2^11-1 = 3 mod 14
      > 2^12-1 = 7 mod 14
      >
      >
      > This would tend to suggest some association between powers of 2 and
      > 14, which, in my limited knowledge, I was unaware of.
      >
      > If anyone can shed some light on this for me it would be much
      > appreciated.

      Since 14 is composite, the first obvious step is to split it to 2*7, consider
      the separate cases, and reconstruct using the Chinese Remainder Theorem in
      the end.

      The case of 2^n - 1 mod 2 is pretty easy, since 2^n == 0 for any n, so 2^n - 1
      == -1 == 1 mod 2.

      Now I claim that powers of 2 take on only 3 different values modulo 7. If you
      know group theory, the explanation is easy: the order of 2 in (Z/7Z)* is 3,
      because 2^3 == 1 mod 7. A non-group theoretic proof is this: write an
      arbitrary integer, say k, as k = 3q + r, where 0 <= r < 3. Now 2^k == 2^(3q +
      r) == 2^(3q) 2^r == (2^3)^q 2^r mod 7. Given that 2^3 == 1 mod 7, we have
      (2^3)^q 2^r == 1^q 2^r == 2^r mod 7, proving that the three values above are
      the only admissible ones.

      I just proved that 2^n can only take on 3 values mod 7, and I hope it's clear
      that 2^n - 1 mod 7 can also take on only 3 values. These values are 2^0 - 1
      == 1 - 1 == 0 mod 7, 2^1 - 1 == 2 - 1 == 1 mod 7, 2^2 - 1 == 4 - 1 == 3 mod
      7. Using the CRT, we have

      (1 mod 2, 0 mod 7) == 7 mod 14,
      (1 mod 2, 1 mod 7) == 1 mod 14,
      (1 mod 2, 3 mod 7) == 3 mod 14.

      So 2^(3q) - 1 == 7 mod 14, 2^(3q + 1) - 1 == 1 mod 14 and 2^(3q + 2) - 1 == 3
      mod 14. You can check that this result corresponds to your findings.

      Décio


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.