 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   A Mersenne number exercise (https://www.mersenneforum.org/showthread.php?t=22904)

 lukerichards 2018-01-09 12:00

A Mersenne number exercise

Hi,
I've seen the following statement in a paper but I don't have access to the reference given. Could someone maybe help me with a proof, please?

[QUOTE]
If:
p is a prime > 2
M[SUB]p[/SUB] = 0 mod q
Then:
q = 1 mod p
and
q = +- mod 8
[/QUOTE]

Not sure where to start?

 Nick 2018-01-09 12:32

Hint: for any odd prime number q, 2 is a square (mod q) if and only if $$q\equiv\pm1\pmod{8}$$.

 Nick 2018-01-10 13:30

As this is related to Mersenne numbers, let's turn it into an exercise for anyone interested.

1. Show for all positive integers m,n that if m divides n then $$2^m-1$$ divides $$2^n-1$$.

Let q be an odd prime number.
2. Show for all positive integers m,n with m>n that if q divides $$2^m-1$$ and q divides $$2^n-1$$ then q divides $$2^{m-n}-1$$.

Let p be an odd prime number as well and suppose that q divides $$2^p-1$$.
3. Show for all positive integers n that q divides $$2^n-1$$ if and only if p divides n.
4. Conclude that $$q\equiv 1\pmod{p}$$.
5. Show that 2 is a square in the integers modulo q, and conclude that $$q\equiv\pm1\pmod{8}$$.
For the last part, the first example [URL="http://www.mersenneforum.org/showthread.php?t=21989"]here [/URL]may be useful.

 ewmayer 2018-01-11 01:03

Nothing like a little quadratic-residuacity exercise to get the new(ish) year off to a good start, eh?

 lukerichards 2018-01-14 20:53

[QUOTE=Nick;477146]As this is related to Mersenne numbers, let's turn it into an exercise for anyone interested.

1. Show for all positive integers m,n that if m divides n then $$2^m-1$$ divides $$2^n-1$$.[/QUOTE]
I think this is sufficient?
NB Spoiler below.

If [TEX] f(x, n) = \sum_{k=1}^{(x)} (2^{n})^{k-1} [/TEX]

Then, for example:
[TEX]\ f(3, n) = (2^{n})^2 + (2^{n}) + 1 [/TEX]

[TEX] f(x, n) [/TEX] is an integer for all integer values of x and n.
And:
[TEX] ({2^n} - 1)f(3, n) = (2^{n})^3 - 1 [/TEX]

Generalised:

[TEX]({2^n} - 1)f(x, n) = (2^{n})^x - 1 [/TEX]
This is an integer for all integer values of n and x.

Now, if n|m, then m = x * n, where m, n and x are all integers.

So:

[TEX]2^{m} = 2^{xn} = (2^n)^x[/TEX]

Therefore:

[TEX]2^{m} - 1 = 2^{xn} - 1 = (2^n)^x - 1[/TEX]

As above:

[TEX] (2^n)^x - 1 = ({2^n} - 1)f(x, n) [/TEX]

It follows:

[TEX] \frac{(2^n)^x - 1}{({2^n} - 1)}\ = f(x, n) [/TEX]

So:

[TEX] \frac{2^m - 1}{({2^n} - 1)}\ = f(x, n) [/TEX]

And f(x) is an integer, so [TEX]M_n[/TEX] divides [TEX]M_m[/TEX] when n divides m.

 science_man_88 2018-01-14 21:22

[QUOTE=lukerichards;477536]I think this is sufficient?
NB Spoiler below.

If [TEX] f(x, n) = \sum_{k=1}^{(x)} (2^{n})^{k-1} [/TEX]

Then, for example:
[TEX]\ f(3, n) = (2^{n})^2 + (2^{n}) + 1 [/TEX]

[TEX] f(x, n) [/TEX] is an integer for all integer values of x and n.
And:
[TEX] ({2^n} - 1)f(3, n) = (2^{n})^3 - 1 [/TEX]

Generalised:

[TEX]({2^n} - 1)f(x, n) = (2^{n})^x - 1 [/TEX]
This is an integer for all integer values of n and x.

Now, if n|m, then m = x * n, where m, n and x are all integers.

So:

[TEX]2^{m} = 2^{xn} = (2^n)^x[/TEX]

Therefore:

[TEX]2^{m} - 1 = 2^{xn} - 1 = (2^n)^x - 1[/TEX]

As above:

[TEX] (2^n)^x - 1 = ({2^n} - 1)f(x, n) [/TEX]

It follows:

[TEX] \frac{(2^n)^x - 1}{({2^n} - 1)}\ = f(x, n) [/TEX]

So:

[TEX] \frac{2^m - 1}{({2^n} - 1)}\ = f(x, n) [/TEX]

And f(x) is an integer, so [TEX]M_n[/TEX] divides [TEX]M_m[/TEX] when n divides m.[/QUOTE]

There are
[SPOILER]SPOILER[/SPOILER]
tags

But I know I can beat that in simplicity.

[SPOILER]Note the reccurence:

[TEX]M_n=2M_{n-1}+1=2M_{n-1}+M_1[/TEX]

This leads to [TEX]2^y(M_n)+M_y=M_{n+y}[/TEX] which when reccursively applied shows the statement.[/SPOILER]

 lukerichards 2018-01-14 21:48

[QUOTE=science_man_88;477538]There are
[SPOILER]SPOILER[/SPOILER][/QUOTE]

Which, when used, ruin the latex :P

 Nick 2018-01-15 15:03

[QUOTE=lukerichards;477536]I think this is sufficient?...[/QUOTE]
Yes, that's fine.
You can also visualize it by writing the numbers in binary.
For example, $$2^4-1$$ is a factor of $$2^{12}-1$$ as
$\underbrace{1111}\underbrace{1111}\underbrace{1111}=1111\times 100010001$

 lukerichards 2018-01-15 15:21

I want to start thinking about the next point, but I've got actual work to do during the day!

 Nick 2018-01-15 15:26

[QUOTE=science_man_88;477538]Note the recurrence...[/QUOTE]
Nice!

 science_man_88 2018-01-15 20:02

[QUOTE=Nick;477586]Nice![/QUOTE]

Not only that, this solves ( or at least heuristics) the first 3 all wihout direct invocation of fermat's little theorem.

1) noted above.
2)see formula from 1, M_m= 2^{m-n}M_n+M_{m-n} q divides the first term, and so q must divide into the second term in order to divide the LHS.
3) following from 2, if q divides other mersennes other than multiples, it follows there is no minimal p, this leads to the absurdity that 1/ q is integer.

All times are UTC. The time now is 21:01.