[seqfan] Re: An unknown problem

[Tomasz Ordowski]

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/
>