## Re: [PrimeNumbers] Mersennes mod 14 question

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

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.