[seqfan] Re: An unknown problem

[Trizen]

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