[seqfan] Re: Digital question
Juan Arias de Reyna
arias at us.es
Thu Feb 24 09:58:36 CET 2011
Here is the proof of
(d does not divide b^2-1) => there exists n with d | n but not d | n_1.
Assume that (d does not divide b^2-1) we want to prove that there exists n with
d | n but not d | n_1.
(a) We may assume that gcd(d,b)=1. In other case d = d_1*d_2 with gcd(d_1,b)=1
d_2 | b^k for a suitable k. Now (d_1 does not divide b^2-1) and if we find
n with d_1 | n but not d_1 | n_1. Take m=n*b^k it is clear that d | m and
m_1 = n_1, so that d does not divide m_1.
(b) Let e the least natural number with d | b^e-1. We will have e > 2, since
d does not divide b^2 -1 and hence also does not divide b-1.
Let x_0=1, x_1, x_2, x_{e-1} , defined by x_j is the rest of b^j mod d.
The usual criterion of divisibility gives us d | n is equivalent to
d | A_0+A_1*x_1+A_2*x_2+ ... + A_{e-1}*x_{e-1} where if A_j = a_j+a_{j+e}+a_{j+2e}+...
are the sum of the digits of the representation of n in base b.
Given elements (z_j)_{j=0}^{e-1} in Z/(dZ) it is easy to construct a number n such that
A_j(n)\equiv z_j mod d and A_j(n_1) equiv z_{e-j-1} mod d. Therefore we only need to construct
elements z_j in Z/(dZ) such that z_0+z_1*x_1+z_2*x_2+ ... + z_{e-1}*x_{e-1}=0 and
z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} != 0
Assume that e is odd. e = 2f+1 then take z_0 = 0, z_f = -b^f, z_{e-1}=1 and all other
z_j = 0. Then
z_0+z_1*x_1+z_2*x_2+ ... + z_{e-1}*x_{e-1} = -b^f x_f+x_{2f} = -b^f b^f + b^(2f) = 0
and
z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} =1 - b^f x_f = 1-b^(2f) != 0
since b^e = b^(2f+1) is the first power of b equal to 1.
Assume now that e is even e = 2f. Since e >2 we have e >= 4.
In this case take z_0 = -b^f, z_{f-1} = b, z_f = 0, z_{2f-1}=0. Then we will have
z_0+z_1*x_1+z_2*x_2+ ... + z_{e-1}*x_{e-1} = -b^f + b x_{f-1} = -b^f + b^f = 0
and
z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} = b x_f - b^f x_{e-1} =
b^(f+1) - b^f b^(2f-1) = b^(f+1) - b^(f-1) = b^(f-1) (b^2-1) != 0.
This ends the proof.
Regards,
Juan Arias de Reyna
El 23/02/2011, a las 01:05, David Wilson escribió:
> Very good. Now show
>
> (d does not divide b^2-1) => there exists n with d | n but not d | n_1.
>
>
> ----- Original Message ----- From: "Vladimir Shevelev" <shevelev at bgu.ac.il>
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Sent: Tuesday, February 22, 2011 7:33 AM
> Subject: [seqfan] Re: Digital question
>
>
>> From b^(t-1)*n-n_1==0 (mod d) we conclude that d | n => d | n_1. Since {n_1 is inv. n}<=>
>> {n is inv. n_1}, then also b^(t-1)*n_1-n==0 (mod d) and we conclude that d | n_1 => d | n.
>>
>> Regards,
>> Vladimir
>
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 10.0.1204 / Virus Database: 1435/3459 - Release Date: 02/22/11
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list