[seqfan] Re: An unknown problem
Tomasz Ordowski
tomaszordowski at gmail.com
Sun Oct 14 17:29:51 CEST 2018
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/
>
More information about the SeqFan
mailing list