[seqfan] Fwd: Converse
Tomasz Ordowski
tomaszordowski at gmail.com
Wed Apr 18 14:07:16 CEST 2018
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>
>
More information about the SeqFan
mailing list