20180109, 12:00  #1  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} 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
2^{4}·101 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
3120_{8} 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·7·829 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
440_{8} 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
2^{4}·101 Posts 

20180115, 15:21  #9 
"Luke Richards"
Jan 2018
Birmingham, UK
120_{16} 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
3120_{8} Posts 

20180115, 20:02  #11 
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} 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 