[seqfan] Re: Converse

[Emmanuel Vantieghem]

If  a = 2^n - 1  is pseudoprime to the base  2
then : 2^a - 2  is divisible by  a
Thus, 2^(a-1) - 1  is divisible by  a (since  a  is odd).
But, when  2^x - 1  is divisible by  2^n - 1, the number  x  is a multiple
of  n.
(otherwise we would have  x = k*n + r  with  r < n  and then :
    2^x - 1 = 2^r*(2^(k*n)) - 2^r + 2^r - 1
               = 2^r*(2^(k*n) - 1) + (2^r - 1) == 0 (mod 2^n - 1),
impossible. ).
Thus, a - 1  is divisible by  n, which proves your conjecture.


2018-04-17 13:36 GMT+02:00 Tomasz Ordowski <tomaszordowski at gmail.com>:

> Hello!
>
> Let us define:
>
> Numbers n such that 2^n == 2 (mod n).
>
> Theorem: if n is such a number,
>     then 2^n-1 is such a number.
>
> Problem: is the reverse theorem true?
>  The converse holds up to n = 10000.
>
> Generally:
>
> Let B be the set of natural numbers n such that
>
>          (b^n-1)/(b-1) == 1 (mod n)
>
> with a fixed integer b > 1.
>
> Conjecture:
>
> The number (b^k-1)/(b-1) belongs to B if and only if k belongs to B.
>
> Note: This can be extended to bases b < -1.
>
> Do you have an idea how to prove my conjecture?
> Professor Pomerance does not know a proof.
> Please reply, it's important to me!
>
> Sincerely,
>
> Thomas Ordowski
> ________________________
> Steuerwald's theorem (1948):
> If k is a psp(b) and gcd(k,b-1)=1, then (b^k-1)/(b-1) is a psp(b).
> Here a composite k is a psp(b) if and only if b^k == b (mod k).
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>