 mersenneforum.org > Math Two points
 Register FAQ Search Today's Posts Mark Forums Read  2012-12-10, 05:50 #1 devarajkandadai   May 2004 22×7×11 Posts Two points This is with reference to my number theory video presentation on You tube: 1) Let p be a prime and M_p be the corresponding Mersenneprime .Consider f(n) = a^n + c where a,n & c belong to N, a & c are fixed. Then if p is not a factor of f(n) for any value of n then M_p also cannot be a factor of f(n) for any value of n, however large. 2) The converse is not true. A.K. Devaraj   2012-12-10, 06:47   #2
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

56610 Posts Quote:
 Originally Posted by devarajkandadai This is with reference to my number theory video presentation on You tube: 1) Let p be a prime and M_p be the corresponding Mersenneprime .Consider f(n) = a^n + c where a,n & c belong to N, a & c are fixed. Then if p is not a factor of f(n) for any value of n then M_p also cannot be a factor of f(n) for any value of n, however large.
I didn't fully understand this. I think its the part "a,n & c belong to N". What is "N"? Sorry for asking basic questions.   2012-12-10, 07:20 #3 LaurV Romulan Interpreter   Jun 2011 Thailand 23·11·97 Posts Let p=2. Then Mp=3. Let f(n)=2^n+1. All f(n) are odd, so they can't be divisible by 2. Don't tell me that 2^3+1 (and generally 2^(2k+1)+1) is not divisible by 3.... edit: @Ake, we assume N is the set "0,1,2..." of natural numbers. Last fiddled with by LaurV on 2012-12-10 at 07:23   2012-12-10, 07:36 #4 Batalov   "Serge" Mar 2008 Phi(3,3^1118781+1)/3 3·31·97 Posts 2) What was meant to be the converse? if reversing the roles of p and M_p, then take p=2, a=3, c=1...   2012-12-10, 08:28   #5
axn

Jun 2003

107578 Posts Quote:
 Originally Posted by devarajkandadai 1) Let p be a prime and M_p be the corresponding Mersenneprime .Consider f(n) = a^n + c where a,n & c belong to N, a & c are fixed. Then if p is not a factor of f(n) for any value of n then M_p also cannot be a factor of f(n) for any value of n, however large.
If p | Mp, then this would be trivially true. But since p | Mp-1, this is unlikely to be true. And LaurV has already given a counterexample.

In fact, if you construct f(n) = p^n+1, the first part (p not being a factor) is trivially satisfied. If the order of p (mod Mp) is even, then there'll be an f(n) which is divisible by Mp.   2012-12-10, 10:13   #6
LaurV
Romulan Interpreter

Jun 2011
Thailand

23×11×97 Posts Quote:
 Originally Posted by axn If p | Mp, then this would be trivially true. But since p | Mp-1, this is unlikely to be true. And LaurV has already given a counterexample. In fact, if you construct f(n) = p^n+1, the first part (p not being a factor) is trivially satisfied. If the order of p (mod Mp) is even, then there'll be an f(n) which is divisible by Mp.
Indeed, take p=7, then Mp=127. There is no f(n)=7^n+1 to be divisible by 7, all are 1 (mod 7), but 7^63+1 is divisible by 127.

Last fiddled with by LaurV on 2012-12-10 at 10:19   2012-12-11, 03:51   #7

May 2004

30810 Posts Two points

Quote:
 Originally Posted by LaurV Let p=2. Then Mp=3. Let f(n)=2^n+1. All f(n) are odd, so they can't be divisible by 2. Don't tell me that 2^3+1 (and generally 2^(2k+1)+1) is not divisible by 3.... edit: @Ake, we assume N is the set "0,1,2..." of natural numbers.
I presume I should have said let p be an odd prime. Secondly the base, a, can only be 2 since Mersenne primes have a meaning only when base is 2.

Example: 2^n+5 is not divisible by 5 for any value of n. 2^n + 5 is not divisible by 31, the relevant M_p, for any value of n.   2012-12-11, 04:10   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

23×11×97 Posts Quote:
 Originally Posted by devarajkandadai I presume I should have said let p be an odd prime. Secondly the base, a, can only be 2 since Mersenne primes have a meaning only when base is 2. Example: 2^n+5 is not divisible by 5 for any value of n. 2^n + 5 is not divisible by 31, the relevant M_p, for any value of n.
Well, "any theory is good if, to confirm it, we need to scrap no more then 50% of the experimental findings." (from the Murphy's collection).
How about p=5, Mp=31, a=2, c=15, does this satisfy your hypothesis? Or you will now start imposing supplementary conditions to the "c" parameter too? Because if 2^n+5 is not divisible by 5 (and indeed is not, as 2^n is not, and 5 it is), I just added 10 to it and get 2^n+15 again, not divisible by 5 for any n. But the trick is that I found out 2^4+5 was 21, so by adding 10 we get 2^4+15 is divisible to 31... And generally, because of the periodicity of 2^n to 31, we get 2^(5k+4)+15 is always divisible to 31, for any k.

Last fiddled with by LaurV on 2012-12-11 at 04:15   2012-12-11, 04:15   #9

May 2004

22×7×11 Posts Two points

Quote:
 Originally Posted by Batalov 2) What was meant to be the converse? if reversing the roles of p and M_p, then take p=2, a=3, c=1...
Example: 2^n+7 is divisible by 5 for some values of n. It is not divisible by 31, the relevant M_p, for any value of n. This shows that the converse is not true.   2012-12-11, 04:29   #10
LaurV
Romulan Interpreter

Jun 2011
Thailand

23·11·97 Posts Quote:
 Originally Posted by devarajkandadai Example: 2^n+7 is divisible by 5 for some values of n. It is not divisible by 31, the relevant M_p, for any value of n. This shows that the converse is not true.
Man, that is not the converse.
An anyhow, what you are trying to do is trivial, if even me can understand it The order of 2 in any prime p is a factor of p-1. The order of 2 in any Mp is p. As p and p-1 are always coprime, you can always find values which satisfy all 4 combinations (x,y), (x,not y), (not x, y) and (not x, not y).
For example, the order of 2 in 5 is 4, because 2^1=2, 2^2=4, 2^3=3, 2^4=1, then they repeat 2-4-3-1-...-2-4-3-1 (mod 5). The order of 2 in 2^5-1=31 is 5, the string is 2-4-8-16-1. Now if you chose convenient c, say c=4, the strings become 2+4, 4+4, 3+4, 1+4, i.e 1-3-2-0 (mod 5) respective 6,8,12,20,5 (mod 31). You are now in the case (x, not y), i.e. sometimes 5 divides 2^n+4, but 31 never divides 2^n+4.

Take another c and you find other case. If c=0 (mod 5) then the first string stays always 2-4-3-1 and there will be no n for which 2^n+5k is divisible by 5. But now if the same c is 29,27,23,15 or 30 mod 31, then sometime 2^n+c will divide even to 31. If you take c=5,10,20,25,35,40,45,50,55,65,etc (i.e. i skipped 15, 30 and 60, to be 0 mod 5 and not 15,30,29 mod 31) then your "theorem" is true. If only.

Last fiddled with by LaurV on 2012-12-11 at 05:20   2012-12-12, 13:50 #11 devarajkandadai   May 2004 22×7×11 Posts Two points The fact remains that no counter has been furnished to my statement that if p is a given odd prime such that its M_p the relevant Mersenne prime exists and if f(n)= 2^n + c( where c is fixed ) is not divisible by p then certainly 2^n + c is not divisible by M_p, however large n may be.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post bsquared Factoring 24 2016-01-25 05:09 aketilander Operazione Doppi Mersennes 6 2012-11-04 12:56 Unregistered Information & Answers 14 2011-09-27 05:34 davieddy Puzzles 7 2007-09-04 12:50 Mystwalker Prime Sierpinski Project 6 2006-01-03 23:32

All times are UTC. The time now is 13:47.

Fri May 29 13:47:53 UTC 2020 up 65 days, 11:20, 1 user, load averages: 1.81, 2.09, 2.40