mersenneforum.org > Math Is this to prove/already known?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-25, 19:22 #1 MatWur-S530113     Apr 2007 Spessart/Germany 2×34 Posts 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
 2007-06-25, 21:12 #2 MatWur-S530113     Apr 2007 Spessart/Germany 2·34 Posts 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
2007-06-26, 10:58   #3
maxal

Feb 2005

111111002 Posts

Quote:
 Originally Posted by MatWur-S530113 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$.

2007-06-27, 04:26   #4
MatWur-S530113

Apr 2007
Spessart/Germany

2·34 Posts

Quote:
 Originally Posted by maxal 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

2007-06-27, 05:35   #5
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by MatWur-S530113 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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post George M Miscellaneous Math 5 2018-01-02 11:11 PawnProver44 Miscellaneous Math 40 2016-03-19 07:33 siegert81 Math 2 2014-11-19 10:24 Damian Math 31 2008-10-03 02:11 mdjvz Software 4 2003-09-28 17:13

All times are UTC. The time now is 18:34.

Fri Dec 4 18:34:49 UTC 2020 up 1 day, 14:46, 0 users, load averages: 1.59, 1.53, 1.51