[seqfan] Fwd: Converse

[Tomasz Ordowski]

Max,

Thank you very much for the generalization.

Thomas,

The proof is valid and can be easily modified for the general case.

Let N=(b^n-1)/(b-1). Then (b^N-1)/(b-1)-1=(b^N-b)/(b-1) is divisible by N
iff b^N-b is divisible by b^n-1. Since

b^N-b == b^(N mod n)-b (mod b^n - 1),

we have that b^N-b is divisible by b^n-1 iff N==1 (mod n). QED

Regards,

Max A. Alekseyev
Associate Professor
George Washington University
Department of Mathematics &
Computational Biology Institute
45085 University Dr. #305
<https://maps.google.com/?q=45085+University+Dr.+%23305+Ashburn,+VA+20147&entry=gmail&source=g>
Ashburn, VA 20147
<https://maps.google.com/?q=45085+University+Dr.+%23305+Ashburn,+VA+20147&entry=gmail&source=g>
http://home.gwu.edu/~maxal
+1-571-5530259


On Wed, Apr 18, 2018, 7:19 AM Tomasz Ordowski <tomaszordowski at gmail.com>
wrote:

> Dear Professor Odlyzko!
>
> Thank you for your reply.  Someone else dared.
> I am asking for a review of the proof sent to me:
>
> 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.
>
> Is it complete?
>
> Sincerely,
>
> Thomas Ordowski
>
> 2018-04-17 15:48 GMT+02:00 Andrew Odlyzko <odlyzko at umn.edu>:
>
>> Tomasz,
>>
>> Interesting.  I just don't know, and without serious study
>> don't have any good heuristics one way or another.
>>
>> best regards,
>> Andrew
>>
>>
>> Tomasz Ordowski <tomaszordowski at gmail.com> wrote:
>>
>> > Dear Professor Odlyzko!
>> >
>> > Let's 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 the set 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).
>>
>
>
>
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> Wolny
> od wirusów. www.avg.com
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
> <#m_9030640719574962937_m_8720914495963573860_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>