20180109, 12:00  #1  
"Luke Richards"
Jan 2018
Birmingham, UK
120_{16} Posts 
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:


20180109, 12:32  #2 
Dec 2012
The Netherlands
1,423 Posts 
Hint: for any odd prime number q, 2 is a square (mod q) if and only if \(q\equiv\pm1\pmod{8}\).

20180110, 13:30  #3 
Dec 2012
The Netherlands
1,423 Posts 
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 here may be useful. Last fiddled with by Nick on 20180110 at 16:09 Reason: Clarification 
20180111, 01:03  #4 
∂^{2}ω=0
Sep 2002
República de California
2^{2}×2,851 Posts 
Nothing like a little quadraticresiduacity exercise to get the new(ish) year off to a good start, eh?

20180114, 20:53  #5  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Quote:
NB Spoiler below. If Then, for example: is an integer for all integer values of x and n. And: Generalised: 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: Therefore: As above: It follows: So: And f(x) is an integer, so divides when n divides m. Last fiddled with by lukerichards on 20180114 at 20:56 

20180114, 21:22  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
SPOILER tags But I know I can beat that in simplicity. 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. Last fiddled with by science_man_88 on 20180114 at 21:50 

20180114, 21:48  #7 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 

20180115, 15:03  #8 
Dec 2012
The Netherlands
1,423 Posts 

20180115, 15:21  #9 
"Luke Richards"
Jan 2018
Birmingham, UK
288_{10} Posts 
I want to start thinking about the next point, but I've got actual work to do during the day!

20180115, 15:26  #10 
Dec 2012
The Netherlands
1,423 Posts 

20180115, 20:02  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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. Last fiddled with by science_man_88 on 20180115 at 20:03 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exercise for gaming time  jasong  jasong  7  20130920 11:20 
Is an online exercise game not based on trust doable?  jasong  jasong  1  20130407 05:55 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Number of Factors for a Mersenne Number  kurtulmehtap  Math  12  20100503 14:02 
Exercise 1.23 in Crandall & Pomerance  sean  Factoring  2  20061023 21:08 