Is this to prove/already known?

MatWur-S530113 · 2007-06-25, 19:22

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 · 2007-06-25, 21:12

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

maxal · 2007-06-26, 10:58

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$ .

MatWur-S530113 · 2007-06-27, 04:26

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

maxal · 2007-06-27, 05:35

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.

2007-06-25, 19:22	#1
MatWur-S530113 Apr 2007 Spessart/Germany 162₁₀ 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

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

2007-06-25, 21:12	#2
MatWur-S530113 Apr 2007 Spessart/Germany 2×3⁴ 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