[seqfan] Re: Theorem -- Extension to negative bases

Andrew N W Hone A.N.W.Hone at kent.ac.uk
Tue Apr 24 00:19:23 CEST 2018


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/



More information about the SeqFan mailing list