mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)

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

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=MatWur-S530113;108965]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$$[/QUOTE]

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=maxal;109003]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$$.[/quote]

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...:blush:)

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

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...:blush:)[/quote]

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=MatWur-S530113;109093]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}$$).[/quote]

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.

 All times are UTC. The time now is 17:50.