[seqfan] Re: Theorem : "two in one"

Tomasz Ordowski tomaszordowski at gmail.com
Tue Apr 24 07:24:07 CEST 2018


Dear Andrew!

Thank you for the proof.

Thus, the theorem can be written in two forms, namely:

Let integer b <> 1 and n be a positive integer. Define N = (b^n-1)/(b-1).

(*) Then b^(N-1) == 1 (mod (b-1)N) if and only if b^n == b (mod (b-1)n).

(**) Then b^N == b (mod (b-1)N) if and only if b^n == b (mod (b-1)n).

Any comments are welcome.

Best regards,

Thomas

2018-04-24 0:19 GMT+02:00 Andrew N W Hone <A.N.W.Hone at kent.ac.uk>:

> Dear Thomas,
>
> The proof of this conjecture follows directly from the neat proof of the
> main result by Max Alekseyev for any b as given here
>
> http://list.seqfan.eu/pipermail/seqfan/2018-April/018629.html
>
> and from a comment that I made about the sequences of n_j in my previous
> message.
>
> The proof is as follows:
>
> Let N = (b^n-1)/(b-1). Suppose that (b^(N-1)-1)/(b-1) == 0 (mod N). Then
> multiplying though by b implies
> (b^N-1)/(b-1) == 1 (mod N), hence by the theorem it follows that
> (b^n-1)/(b-1) == 1 (mod n).
>
> Conversely, suppose that (b^n-1)/(b-1) == 1 (mod n). So (b^N-1)/(b-1) == 1
> (mod N) by the theorem,
> hence
>
> (b^N-b)/(b-1) == 0 (mod N),
>
> but N == 1 (mod b) from the definition of N, therefore b is coprime to N,
> so dividing by b above gives the required result.
>
> Cheers,
> Andy
>
> ________________________________________
> From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Tomasz Ordowski
> [tomaszordowski at gmail.com]
> Sent: 23 April 2018 12:43
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Theorem -- Extension to negative bases
>
> Dear Andrew!
>
> Thank you for being the only one who took part in the discussion.
>
> This theorem can be formulated without the set B, namely:
>
> Let integer b <> 1 and n be a positive integer. Define N = (b^n-1)/(b-1).
>
> Theorem:
> (b^N-1)/(b-1) == 1 (mod N) if and only if (b^n-1)/(b-1) == 1 (mod n).
>
> Conjecture:
> (b^(N-1)-1)/(b-1) == 0 (mod N) if and only if (b^n-1)/(b-1) == 1 (mod n).
>
> This conjecture is true for b = 2.
> Are there counterexamples for other b?
> Maybe someone will try to prove it or disprove it?
>
> Best regards,
>
> Thomas
>
> 2018-04-23 13:11 GMT+02:00 Andrew N W Hone <A.N.W.Hone at kent.ac.uk>:
>
> > Dear Thomas,
> >
> > Just a few comments on your discussion.
> >
> > It makes sense to denote the set as B(b), to indicate the dependence on
> b.
> >
> > The aforementioned proof of the theorem that
> >
> > n belongs to B(b) if and only if N=(b^n-1)/(b-1) belongs to B(b)
> >
> > is equally valid for negative b. (Note also that n belongs to B(-b) if
> and
> > only if it belongs to B(n-b).)
> >
> > In fact the definition of the set is equivalent to the following:
> >
> > n belongs to B(b) if and only if b^n == b (mod n) and gcd(b-1,n)=1.
> >
> > Also the original definition of the set can be stated without division,
> as
> >
> > n belongs to B(b) if and only if b^{n-1}+b^{n-2}+...+ b == 0 (mod n),
> >
> > and the latter two definitions are valid for any integer b.
> >
> > So the set B(b) is the union
> >
> > B(b) = { primes } \cup { pseudoprimes to base b } \cup { divisors of b },
> >
> > where the pseudoprimes are the composite n such that b^{n-1} - 1 == 0
> (mod
> > n).
> >
> > The case of B(0) is trivial: it consists of all natural numbers.
> >
> > With the above alternative definitions, the set B(1) is also defined: it
> > is a set with just one element, {1}.
> >
> > The set B(-1) consists of all odd natural numbers.
> >
> > So the only interesting cases are when |b|>1.
> >
> > For a fixed b, it might be interesting to look for pseudoprimes by using
> > the above theorem. For example, starting from any divisor of b, n_0>1,
> one
> > can recursively construct
> >
> > n_{j+1} = (b^{n_j}-1)/(b-1),
> >
> > for j=0,1,2,... It is easy to see that gcd(n_j,b)=1 for j>=1. Similarly
> > one can start with n_0 any prime. Many of the terms n_j will be prime,
> but
> > sometimes pseudoprimes appear. I don't know what proportion of terms in
> the
> > sequence goes between prime/pseudoprime, but it might be interesting to
> > find out.
> >
> > Example 1: for b=2, start with n_0=2, then n_1=3, n_2=7, n_3=127,
> > n_4=2^{127}-1 are all (Mersenne) primes. Where does the first pseudoprime
> > appear? (This can be checked quickly with the Lucas-Lehmer test.)
> >
> > Example 2: for b=3, start with n_0=3, then n_1=121 (pseudoprime to base
> > 3), n_2 = (3^{121}-1)/2 is another pseudoprime (it is divisible by 23);
> can
> > one say anything about whether subsequent terms are prime or not?
> >
> > Anyway, it looks quite fun, and may lead to some new sequences!
> >
> > All the best,
> > Andy
> >
> >
> >
> > ________________________________________
> > From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Tomasz
> Ordowski
> > [tomaszordowski at gmail.com]
> > Sent: 19 April 2018 10:19
> > To: Sequence Fanatics Discussion list
> > Subject: [seqfan] Theorem -- Extension to negative bases
> >
> > Dear SeqFans!
> >
> > Let me remind you of the proven generalization:
> >
> > 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.
> >
> > Then, the number (b^k-1)/(b-1) belongs to the set B
> > if and only if k belongs to B.
> >
> > The questions: How to extend this theorem to the integer bases b < -1 ?
> > It should work with every integer b <> 1.  How will it be for b = 0 and
> -1
> > ?
> > Is it necessary to assume that n is odd for b < -1 ?
> >
> > Best regards,
> >
> > Thomas
> >
> > P.S. A comment:
> >   http://oeis.org/A015919
> > If 2^k-1 is a term, then so is k.
> > Asymptotic formula: a(n) ~ n log n.
> > I still have a full account on the OEIS.
> >
> >
> >
> > <#m_-1301679863165878748_m_-8214366375184677225_m_
> > 8821574979675864549_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
>
> <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>
> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list