Anti-Carmichael Pairs

Let the integers  a,b  be called an "anti-Carmichael pair" if a divides
b(b-1) and if b divides a(a-1).  This definition was suggested by 
George Baloglou, who gave the example a=63,b=217.  Here's one way of 
characterizing all such pairs:  We want positive integers A,B such 
that A divides B(B-1), and B divides A(A-1), which implies integers 
M,N such that

           A(A-1) = MB            B(B-1) = NA

Let c be the greatest common divisor of A and B, so we have A=ac, B=bc 
where gcd(a,b)=1.  The above equations become

           a(ac-1) = Mb          b(bc-1) = Na

Since a and b are coprime we know that a divides M, and b divides N,
so there are integers n,m such that  M=ma  and  N=nb.  Thus the above
equations reduce to ac-1 = mb and bc-1 = na, which can be written as

             ac - bm = 1        bc - an = 1

Since a and b are coprime we are guaranteed infinitely many solutions
of each of these equations.  The solutions of the left hand equation
will be of the form c = c_0 + bk  and of the right hand will be
c = c_0 + aj, and so the solutions to both equations are of the 
form c = c_0 + (ab)t  for any integer t.  The value of c_0 can be
found via the Euclidean Algorithm applied to either of the above
equations.  Incidentally, also we have the linear equation 

                   a^2 n - b^2 m  =  (b-a)

Anyway, this shows that (A,B) = (ac,bc) is an anti-Carmichael pair 
if and only if

          A = a(c_0 + ab t)      B = b(c_0 + ab t)

for any non-negative integer t, where c_0 is the least positive solution 
of ac-bm=1.  Thus for ANY pair of coprime integers (a,b) we can construct 
the unique infinite family of anti-Carmichael pairs.

For example, let's take a=9 and b=31.   The least positive solution 
of 9c-31m=1 is with c=7, so it follows that any pair of integers of the 
form ( 9(7+279t), 31(7+279t) ) is anti-Carmichael for any non-negative 
integer t.  With t=0 this gives George's (63,217), whereas with t=1 it 
gives (2574,8866), and so on.

Return to MathPages Main Menu
Сайт управляется системой uCoz