## 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