[seqfan] Re: An unknown problem

[Tomasz Ordowski]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Extension of the problem to other bases.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

As is well known:
If p is a prime that does not divide b-1, then (b^p-1)/(b-1) has all
divisors d == 1 (mod p).

Let a(n) be the smallest composite k such that (n^k-1)/(n-1) has all
divisors d == 1 (mod k).

Note that (n^k-1)/(n-1) == 1 (mod k), so n^k == n (mod (n-1)k). Thus a(n)
>= A298908(n).

Cf. https://oeis.org/history/view?seq=A298908&v=25

a(n) is the least composite k such that (n^k-1)/(n-1) has all prime
divisors p == 1 (mod k).

For n > 2, a(n) = 91, 4, 5731, 6, 25, 9, 91, 10, ... Please more. The basic
problem: a(2) = ?

Cf. https://oeis.org/A298076

Can also consider these numbers to negative bases by defining:

Least odd composite k such that (n^k+1)/(n+1) has all divisors d == 1 (mod
k).

Data: 9, 341, 91, ... for n = 1, 2, 3, ... Cf. https://oeis.org/A298310

The most interesting is the base -2, so let's define:

Odd composite numbers k such that (2^k+1)/3 has all divisors d == 1 (mod
k).

I found only two such numbers k = 341 = 11*31 and k = 5461 = 43*127. Please
more.

Theorem:
If both (2^p+1)/3 and (2^q+1)/3 are prime and n = pq is pseudoprime, then n
is such a number k.

Do known the Wagstaf exponents https://oeis.org/A000978 give more such
pseudoprimes?

Does it exhaust all other cases?

Thomas Ordowski
____________________
The numeric coincidence:
These two numbers 341 and 5461 are also Cipolla pseudoprimes:
https://oeis.org/A210454


niedz., 14 paź 2018 o 17:29 Tomasz Ordowski <tomaszordowski at gmail.com>
napisał(a):

> Hello!
>
> Thank you for your interest in my problem.
>
> The problem (equivalently):
>
> Are there composite numbers n such that 2^n - 1 has all divisors d == 1
> (mod n) ?
>
> Contrary to what some people think, this problem is not resolved.
>
> Best regards,
>
> Thomas Ordowski
>
> niedz., 14 paź 2018 o 16:09 Trizen <trizenx at gmail.com> napisał(a):
>
>> Hi, Tomasz. Very interesting problem!
>>
>> I was not able to find any such number bellow 220729.
>>
>> The search was done using Fermat pseudoprimes to base 2 and the
>> observation
>> that if 2^n-1 has a prime factor p < n, we can safely skip it, since p = p
>> (mod n) for p < n.
>>
>> When 2^n - 1 has only prime factors p > n, we try to find the first prime
>> that is not p = 1 (mod n).
>>
>> Bellow I included a list with one such prime factor p | 2^n-1, p > n, for
>> which p != 1 (mod n), listed under the form: p = k (mod n):
>>
>> 535006138814359 = 2314   (mod   4369)
>>           18121 = 4078   (mod   4681)
>>  16937389168607 = 332    (mod  10261)
>>           80929 = 1125   (mod  19951)
>>          931921 = 20828  (mod  31417)
>>        85798519 = 10746  (mod  31621)
>>        10960009 = 1566   (mod  49141)
>>          104369 = 16012  (mod  88357)
>>         1504073 = 38931  (mod 104653)
>>          179951 = 56700  (mod 123251)
>>        13821503 = 53269  (mod 129889)
>>          343081 = 81959  (mod 130561)
>>       581163767 = 26248  (mod 162193)
>>         2231329 = 162702 (mod 188057)
>>         2349023 = 18371  (mod 194221)
>>          326023 = 106242 (mod 219781)
>>
>> Strong candidate: n = 220729
>>    2^n - 1 has no factors bellow 10^9
>>
>> Daniel
>>
>> On Sun, Oct 14, 2018 at 11:24 AM Tomasz Ordowski <
>> tomaszordowski at gmail.com>
>> wrote:
>>
>> > Dear SeqFans!
>> >
>> > The problem:
>> >
>> > Are there composite numbers n such that 2^n - 1 has all prime divisors
>> p ==
>> > 1 (mod n) ?
>> >
>> >   Note: Such a supposed number n must be a Fermat pseudoprime to base 2.
>> >
>> > If both 2^p - 1 and 2^q - 1 are prime and n = pq is pseudoprime, then n
>> is
>> > such a number.
>> >
>> > However, known Mersenne primes do not give such pseudoprimes.
>> >
>> > Best regards,
>> >
>> > Thomas
>> > ______________
>> > There are similar composite numbers n to other bases,
>> > for example 91 = 7*13 to base 3 and 341 = 11*31 to base -2;
>> > the number (3^91-1)/2 has all prime divisors p == 1 (mod 91)
>> > and (2^341+1)/3 has all prime divisors p == 1 (mod 341).
>> > Note that both (3^7-1)/2 and (3^13-1)/2 are prime
>> > and both (2^11+1)/3 and (2^31+1)/3 are prime.
>> >
>> > --
>> > Seqfan Mailing list - http://list.seqfan.eu/
>> >
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>