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? 
Hint: for any odd prime number q, 2 is a square (mod q) if and only if \(q\equiv\pm1\pmod{8}\).

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^m1\) divides \(2^n1\). Let q be an odd prime number. 2. Show for all positive integers m,n with m>n that if q divides \(2^m1\) and q divides \(2^n1\) then q divides \(2^{mn}1\). Let p be an odd prime number as well and suppose that q divides \(2^p1\). 3. Show for all positive integers n that q divides \(2^n1\) 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. 
Nothing like a little quadraticresiduacity exercise to get the new(ish) year off to a good start, eh?

[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^m1\) divides \(2^n1\).[/QUOTE] I think this is sufficient? NB Spoiler below. If [TEX] f(x, n) = \sum_{k=1}^{(x)} (2^{n})^{k1} [/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 nm, 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=lukerichards;477536]I think this is sufficient?
NB Spoiler below. If [TEX] f(x, n) = \sum_{k=1}^{(x)} (2^{n})^{k1} [/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 nm, 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_{n1}+1=2M_{n1}+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] 
[QUOTE=science_man_88;477538]There are
[SPOILER]SPOILER[/SPOILER][/QUOTE] Which, when used, ruin the latex :P 
[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^41\) is a factor of \(2^{12}1\) as \[ \underbrace{1111}\underbrace{1111}\underbrace{1111}=1111\times 100010001 \] 
I want to start thinking about the next point, but I've got actual work to do during the day!

[QUOTE=science_man_88;477538]Note the recurrence...[/QUOTE]
Nice! 
[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^{mn}M_n+M_{mn} 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.