mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-06-25, 19:22   #1
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

A216 Posts
Red face Is this to prove/already known?

Hello,

I got this conjecture last night, but my math is not good enough to prove it...

if and only if n^{n-1} is divisible by ((n-1) / 2)^2 then there is a non-negative Integer k with n=2^k+2 (= M(k) + 3)

another conjecture:
if n>1, n odd then n^{n-1}-1 is divisible by ((n-1)/2)^2

are these conjectures already known/proven? And if not, any idea how to prove them?
I got them while looking in a self-created file with the (start of) factorisations of numbers of the form: n=p^{p-1}-1, p prime (I made TF in this file up to 30 bit, if wanted I'll post it).

Thanks in advance.

mfg

Matthias
MatWur-S530113 is offline   Reply With Quote
Old 2007-06-25, 21:12   #2
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2428 Posts
Default

hmhmhmhm,

something I made wrong. If n=2^k+2 then n is even, then n-1 is odd, then n-1 is not divisible by 2 as needed for ((n-1)/2)^2.
I made the division with a ShR-order, so the last bit was ignored. A corrected form of the first conjecture is:

if and only if n^{n-1} is divisible by (floor((n-1)/2))^2 then there is a non-negative Integer k with n=2^k+2

mfg

Matthias
MatWur-S530113 is offline   Reply With Quote
Old 2007-06-26, 10:58   #3
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
if and only if n^{n-1} is divisible by (floor((n-1)/2))^2 then there is a non-negative Integer k with n=2^k+2
Consider two cases:

1) n is even then m=floor((n-1)/2)=\frac{n-2}{2}.
We have n=2m+2 and 0\equiv n^{n-1}\equiv (2m+2)^{2m+1}\equiv 2^(2m+1)\pmod{m}, implying that m=2^k for some k. Therefore, n=2*2^k+2=2^(k+1)+2.

2) n is odd then m=floor((n-1)/2)=\frac{n-1}{2}.
We have n=2m+1 and 0\equiv n^{n-1}\equiv (2m+1)^{2m}\equiv 1\pmod{m}, implying that m=1 and n=3=2^0+2.
maxal is offline   Reply With Quote
Old 2007-06-27, 04:26   #4
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2×34 Posts
Default

Quote:
Originally Posted by maxal View Post
Consider two cases:

1) n is even then m=floor((n-1)/2)=\frac{n-2}{2}.
We have n=2m+2 and 0\equiv n^{n-1}\equiv (2m+2)^{2m+1}\equiv 2^(2m+1)\pmod{m}, implying that m=2^k for some k. Therefore, n=2*2^k+2=2^(k+1)+2.

2) n is odd then m=floor((n-1)/2)=\frac{n-1}{2}.
We have n=2m+1 and 0\equiv n^{n-1}\equiv (2m+1)^{2m}\equiv 1\pmod{m}, implying that m=1 and n=3=2^0+2.
Many thanks for your reply. But 2 things I don't understand:

1) if 0\equiv 2^{2m+1}\pmod{m} why does this imply that m=2^k for some k? (Probably I miss an easy thought...)

2) if n is even I still don't see why n must have the form n=2^k+2, if n^{n-1} is divisible by m^2=(\frac{n-2}{2})^2 (not only by m=\frac{n-2}{2}).

greetings,

Matthias
MatWur-S530113 is offline   Reply With Quote
Old 2007-06-27, 05:35   #5
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
Many thanks for your reply. But 2 things I don't understand:

1) if 0\equiv 2^{2m+1}\pmod{m} why does this imply that m=2^k for some k? (Probably I miss an easy thought...)
Because 0\equiv 2^{2m+1}\pmod{m} means that m divides a power of 2, namely, 2^{2m+1}. Therefore, m=2^k for some k.

Quote:
Originally Posted by MatWur-S530113 View Post
2) if n is even I still don't see why n must have the form n=2^k+2, if n^{n-1} is divisible by m^2=(\frac{n-2}{2})^2 (not only by m=\frac{n-2}{2}).
If n^{n-1}\equiv 0\pmod{m^2} then n^{n-1}\equiv 0\pmod{m}, and I showed that the latter congruence implies n=2^(k+1)+2 for some k.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
So how must we be able to prove the following? George M Miscellaneous Math 5 2018-01-02 11:11
I have to prove everything PawnProver44 Miscellaneous Math 40 2016-03-19 07:33
How can I prove this PRP prime? siegert81 Math 2 2014-11-19 10:24
Why is RH so difficult to prove? Damian Math 31 2008-10-03 02:11
why not stop when composite is prove? mdjvz Software 4 2003-09-28 17:13

All times are UTC. The time now is 02:59.

Wed Dec 2 02:59:25 UTC 2020 up 83 days, 10 mins, 1 user, load averages: 1.67, 1.45, 1.47

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.