[seqfan] Fwd: A069051 U A330382

[Tomasz Ordowski]

The PROOF of my conjecture,
that 2^(2^n-1) == 2 (mod 2^n-2)
if and only if 2^n == 2 (mod n-1),
by Emmanuel Vantieghem. Thanks!

PROOF of the IF part.
Suppose 2^n == 2 (mod n-1).
Then: 2^n-1 = 1+w(n-1) for some natural number w.
Thus, 2^(2^n-1)-2 = 2^(1+w(n-1))-2 = 2(2^(w(n-1))-1)
   = 2(2^(n-1)-1)(2^((n-1)(w-1))+...+2^(n-1)+1).
Thus, 2^(2^n-1)-2 is divisible by 2^(n-1)-1
and since it is even, it is divisible by 2^n-2. QED.

That was easy. But how to goe back?

PROOF of the CONVERSE.
Suppose 2^(2^n-1)-2 is divisible by 2^n-2.
Then, trivially, 2^(2^n-2)-1 is divisible by 2^(n-1)-1.
If 2^n-2 is not divisible by n-1, then we can write:
   2^n-2 = w(n-1)+r with 0 < r < n-1.
It follows that 2^(w(n-1)+r)-1 == 0 (mod 2^(n-1)-1).
But, 2^(w(n-1)) == 1 (mod 2^(n-1)-1), whence we
then have 2^r-1 is divisible by 2^(n-1)-1, impossible.
Thus... QED.

Sincere greetings,

Emmanuel

wt., 25 cze 2024 o 14:08 Tomasz Ordowski <tomaszordowski at gmail.com>
napisał(a):

> PS. The OEIS has almost everything,
> namely "two in one, but minus one"...
>
> Numbers n-1 such that 2^n == 2 (mod n-1) are A014741.
>
> https://oeis.org/A014741
>
> Prime numbers n are A069051.
> Composite numbers n are A330382.
>
> Conjecture:
> 2^(2^n-1) == 2 (mod 2^n-2)
> if and only if 2^n == 2 (mod n-1).
>
> Either proof or counterexample is welcome!
>
>
> pon., 24 cze 2024 o 23:07 Tomasz Ordowski <tomaszordowski at gmail.com>
> napisał(a):
>
>> Hello!
>>
>> How to prove that
>> 2^(2^n-1) == 2 (mod 2^n-2)
>> if and only if 2^n == 2 (mod n-1) ?
>>
>> Best,
>>
>> Tom Ordo
>>
>> https://oeis.org/A069051
>> https://oeis.org/A330382
>>
>>