mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Is this to prove/already known? (https://www.mersenneforum.org/showthread.php?t=8497)

MatWur-S530113 2007-06-25 19:22

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 [tex]n^{n-1}[/tex] is divisible by [tex]((n-1) / 2)^2[/tex] then there is a non-negative Integer k with [tex]n=2^k+2[/tex] (= M(k) + 3)

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

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: [tex]n=p^{p-1}-1[/tex], 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 [tex]n=2^k+2[/tex] then n is even, then n-1 is odd, then n-1 is not divisible by 2 as needed for [tex]((n-1)/2)^2[/tex].
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 [tex]n^{n-1}[/tex] is divisible by [tex](floor((n-1)/2))^2[/tex] then there is a non-negative Integer k with [tex]n=2^k+2[/tex]

mfg

Matthias

maxal 2007-06-26 10:58

[QUOTE=MatWur-S530113;108965]if and only if [tex]n^{n-1}[/tex] is divisible by [tex](floor((n-1)/2))^2[/tex] then there is a non-negative Integer k with [tex]n=2^k+2[/tex][/QUOTE]

Consider two cases:

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

2) n is odd then [tex]m=floor((n-1)/2)=\frac{n-1}{2}[/tex].
We have n=2m+1 and [tex]0\equiv n^{n-1}\equiv (2m+1)^{2m}\equiv 1\pmod{m}[/tex], implying that [tex]m=1[/tex] and [tex]n=3=2^0+2[/tex].

MatWur-S530113 2007-06-27 04:26

[quote=maxal;109003]Consider two cases:

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

2) n is odd then [tex]m=floor((n-1)/2)=\frac{n-1}{2}[/tex].
We have n=2m+1 and [tex]0\equiv n^{n-1}\equiv (2m+1)^{2m}\equiv 1\pmod{m}[/tex], implying that [tex]m=1[/tex] and [tex]n=3=2^0+2[/tex].[/quote]

Many thanks for your reply. But 2 things I don't understand:

1) if [tex]0\equiv 2^{2m+1}\pmod{m}[/tex] why does this imply that [tex]m=2^k[/tex] 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 [tex]n=2^k+2[/tex], if [tex]n^{n-1}[/tex] is divisible by [tex]m^2=(\frac{n-2}{2})^2[/tex] (not only by [tex]m=\frac{n-2}{2}[/tex]).

greetings,

Matthias

maxal 2007-06-27 05:35

[QUOTE=MatWur-S530113;109093]Many thanks for your reply. But 2 things I don't understand:

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

Because [tex]0\equiv 2^{2m+1}\pmod{m}[/tex] means that m divides a power of 2, namely, [tex]2^{2m+1}[/tex]. Therefore, [tex]m=2^k[/tex] for some k.

[QUOTE=MatWur-S530113;109093]2) if n is even I still don't see why n must have the form [tex]n=2^k+2[/tex], if [tex]n^{n-1}[/tex] is divisible by [tex]m^2=(\frac{n-2}{2})^2[/tex] (not only by [tex]m=\frac{n-2}{2}[/tex]).[/quote]

If [tex]n^{n-1}\equiv 0\pmod{m^2}[/tex] then [tex]n^{n-1}\equiv 0\pmod{m}[/tex], 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.

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