mersenneforum.org

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.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.