[seqfan] Re: Digital question

[Vladimir Shevelev]

Let us separate a nontrivial part of your proof,

If inv(d)<d, then it is sufficient to choose n=d ; if inv(d)>d and not multiple of d, then n=d is required as well. What is the left? d could be either PALINDROMIC (inv(d)=d)  or a number wth the reversal  multiple of d (cf. A031877).  Denote the set of such numbers R_b.
  
Thus from your proof we conclude that, if d is not a divisor of b^2-1, then, for every d \in R_b, there exists  m such that m*d is not only in R_b but even inv(m*d) is not multiple of d.
 
   Maybe, there exists a direct proof of this fact?
 
Thanks,
Vladimir


----- Original Message -----
From: Juan Arias de Reyna <arias at us.es>
Date: Thursday, February 24, 2011 10:59
Subject: [seqfan] Re: Digital question
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> 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/
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎