Solving number theory problems with cyclic and symmetric variables

Abstract

The beauty of many algebraic problems (solving system of equations, proving inequality, ...) comes from the symmetric / cyclic properties of its variables. These properties also exist in a class of number theory problems, but require a different approach to utilize, as the variables in this context are often natural numbers or integers, instead of real numbers. In this article we mention two directions that can be taken into account to solve a variety of cyclic problems. The reader is encouraged to gain familiarity with the technique of Vieta jumping and the concept of p-adic order ν_p(n), both of which are employed throughout this writing.

1 Turning cyclicity into symmetry

If gcd(a,b) = 1, we can construct two functions g : ℤ → ℤ and h : ℤ² → ℤ such that:

for some k ∈ ℤ. (1) is a two-variable equation in terms of a and b. If deg h = 1 we can use inequalities to restrict the domain of a and b to a finite subset of ℤ. If deg h = 2 we can use Vieta jumping to solve (1).

Without gcd(a,b) = 1, we still have ab∣f(a)f(b). We can then expand the RHS and remove all multiples of ab, essentially ending up with an equation similar to (1).

Solution. Let a = p - 1, b = q - 1 then a ≥ b ≥ 1 and

a | 3(b + 1) - 1, b | 3 (a + 1) - 1,

which implies

ab | (3a + 2)(3b + 2) ⇔ ab | 6a + 6b + 4.

As a,b are positive integers, divisibility implies that

6 6 4 6a + 6b + 4 ≥ ab ⇒ --+ --+ ---≥ 1. a b ab

On the other hand, because a ≥ b,

12 4 6 6 4 ---+ -- ≥ --+ --+ ---. b b2 a b ab

We now get a one-variable inequality,

12- 4- 2 b + b2 ≥ 1 ⇔ b - 12b - 4 ≤ 0 ⇔ 1 ≤ b ≤ 12.

Note that b + 1 = q is prime so b ∈{1, 2, 4, 6, 10, 12}. Knowing b, we can easily infer a:


b	Condition for a	Values of a

1	a∣6a + 6 + 4	{1, 2, 10}

2	2a∣6a + 12 + 4	{2, 4}

4	4a∣6a + 24 + 4	{6, 10}

6	6a∣6a + 36 + 4	∅

10	10a∣6a + 60 + 4	{16}

12	12a∣6a + 72 + 4	∅

Hence all possible values of (p,q) are (2, 2); (3, 3); (5, 3); (7, 5); (17, 11). __

Solution. As a∣bc - 31 and a∣a(b + c) we have

a | ab + bc + ca - 31.

Similar arguments apply to b and c. Since a,b,c are pairwise coprime,

abc | ab + bc + ca - 31.

(2)

Now consider the following cases:

a ≥ 3. Then b ≥ 4 and c ≥ 5, so ab + bc + ca > 31. It also follows that $abc ≥ 3bc > ab + bc + ca > ab + bc + ca - 31,$ which contradicts (2). Hence this case does not yield any solution.
a = 2. Then b∣2c - 31 and c∣2b - 31. It follows that $bc | 2b + 2c - 31.$ By similar arguments, we get b = 3 and c = 5.
a = 1. Then b∣c - 31 and c∣b - 31. Note that b + c = 31 satisfies both conditions, and there are a total of 14 tuples (a,b,c) satisfying $( || |||{ a = 1 | b + c = 31 |||| ( a < b < c$ If b + c≠31, we prove that 1 < b,c < 31. Assume otherwise,
- If b > 31 then c > b > b - 31 > 0 so c ∤ b - 31, which is false.
- If b = 31 then 31∣c - 31 so 31∣c. But then gcd(b,c) = 31 > 1, which is false.
- If b < 31 < c then |c| > |b - 31| > 0 so c ∤ b - 31, which is false.
Hence 1 < b < c < 31. Combining with b∣c - 31 and c∣b - 31, we get
$bc | 31 - b - c.$ Further consider the following cases:
- If b ≥ 5 then c ≥ 6 so bc ≥ 30 > 31 - (b + c), which is false.
- If b = 4 then 4∣c - 31 and c∣27, so c = 27. However, this is false since we are assuming b + c≠31.
- If b = 3 then 3∣c - 31 and c∣28, so c ∈{4, 7}.
To sum up, the case a = 1 yields 16 possible values of (b,c).

Hence we conclude that there are in total 17 possible tuples (a,b,c). __

Remark 1. In the previous two examples, we try to arrive at a condition of the form

xy | αx + βy + γ.

We can then use algebraic manipulations to restrict |x| and |y|, since if |x| and |y| gets too large, |xy| will quickly outgrow |αx+βy+γ|, which means the divisibility condition cannot be satisfied. This illustrates our initial point that if deg h = 1 we can use inequalities.
In case deg h > 1, however, pure algebraic manipulations are no longer effective. Instead, an effective way to tackle higher degree polynomials is Vieta jumping.

Solution. From

q | p3 - 1 = (p - 1)(q2 + q + 1)

and q > p > p - 1 we have q∣p² + p + 1.
Also p∣q³ - 1 = (q - 1)(q² + q + 1), so either p∣q - 1 or p∣q² + q + 1.

If p∣q - 1 then let p² + p + 1 = nq where n ∈ ℕ^*. Note that in mod p, q ≡ 1 and p² + p + 1 ≡ 1 so n ≡ 1. Since q ≥ p + 1, we also have $2 ⌊ 2 ⌋ ⌊ ⌋ n = p--+-p +-1 ≤ p-+-p-+-1- = p + --1-- = p, q p + 1 p + 1$ Hence n = 1 and q = p² + p + 1 so p² + p + 1 < 1000. This implies p ≤ 31, since 37² + 37 + 1 > 1000.
We can then brute force to find all values of p and then q. These are $(2,7);(3,13);(5,31);(17,307 ).$

If p∣q² + q + 1 then

	p∣(q² + q + 1) + (p² + p), and
	q∣(p² + p + 1) + (q² + q),

2 2 pq | p + q + p + q + 1.

In other words, for some m ∈ ℕ^* we need to find a,b satisfying

2 2 a + b + a + b + 1 = mab.

(3)

Rewrite (3) as

a2 + (1 - mb ) ⋅ a + (b2 + b + 1) = 0.

Let S be the set of all pairs (a,b) satisfying (3). Consider (a₀,b₀) ∈ S where a₀ + b₀ is smallest. WLOG assume a₀ ≥ b₀.
According to Vieta’s theorem, (3) also has another solution (a′,b₀) where a′ satisfies

a₀ + a′ = mb₀ - 1,		(4)
a₀a′ = b₀² + b₀ + 1.		(5)

(4) implies that a′∈ ℤ, while (5) implies a′ > 0. Hence (a′,b₀) ∈ S. By the definition of (a₀,b₀), we then have

b2 + b + 1 a0 + b0 ≤ a ′ + b0 ⇒ a0 ≤ a ′ =-0--0---- ⇒ b20 + b0 + 1 ≥ a0. a0

If a₀ > b₀ then a₀ ≥ b₀ + 1, so a₀² > (b₀ + 1)² > b₀² + b₀ + 1, which is false. Hence a₀ = b₀, so

2 2 a 0 + (1 - a0) ⋅ a0 + (a 0 + a0 + 1) = 0,

which means a₀∣1 ⇒ a₀ = b₀ = 1. This leads to m = 5. (3) then becomes

a2 + b2 + a + b + 1 = 5ab.

(6)

As we proved earlier, if (a₀,b₀) is a solution then so is (5a₀ - b₀ - 1,a₀). Hence from one solution (1, 1) we get (3, 1), and then (13, 3), ... We can in fact prove that all solutions of (6) are (a_i,b_i) = (x_i+1,x_i) where x_is come from the sequence

( | { x0 = x1 = 1 (xn ) : | ( xn+1 = 5xn - xn- 1 - 1 for n ≥ 1

The proof for this statement is very similar to that of VMO 2012 P6. All that’s left is to find the pairs (x_i+1,x_i) from the above sequence such that x_i and x_i+1 are primes smaller than 1000. It’s easy to observe that i ≤ 4 because x₆ > 1000. We then find (p,q) ∈{(3, 13); (13, 61)}.

In conclusion, all possible values of p and q are (2, 7); (3, 13); (5, 31); (13, 61); (17, 307). __

2 Imposing orders on the variables

If the variables are symmetric, we can sort them in ascending or descending order. If the variables are cyclic, we can point out one variable with some maximum / minimum property.

Solution. Let L and R denote the LHS and RHS of the equality repspectively. Consider an arbitrary prime p. If p ∤ [a,b,c] then it’s obvious that ν_p(L) = ν_p(R) = 0. On the other hand, if p∣[a,b,c] then either p∣a or p∣b or p∣c. Let x = ν_p(a), y = ν_p(b), z = ν_p(c). As a,b,c are symmetric, WLOG assume x ≥ y ≥ z, then

ν_p(L) = y + z + z - 2z = y
ν_p(R) = x + y + x - 2x = y

Hence ν_p(L) = ν_p(R) as well. In other words, for any prime p, ν_p(L) = ν_p(R), so L and R have the same prime factorization. By the fundamental theorem of arithmetic, L = R. __

Solution. WLOG assume p ≤ q. Consider the following cases:

If p = 3 then $q q q q 3q | 117(5 - 2 ) ⇒ q | 39(5 - 2 ).$ According to Fermat’s theorem, 5^q - 2^q ≡ 5 - 2 ≡ 3 (mod q), so it must be the case that q∣39 ⇒ q ∈{3, 13}.
If 5 < p < q then, following similar arguments, we have $5p - 2p ≡ 5 - 2 ≡ 3 (mod p)$ so p∣5^q - 2^q. Further note that 5^p-1 ≡ 2^p-1 ≡ 1 (mod p) so p∣5^p-1 - 2^p-1.
As q > p > p - 1, gcd(q,p - 1) = 1, so there exist m,n ∈ ℕ^* such that
$m ⋅ q - n ⋅ (p - 1 ) = 1 or m ⋅ (p - 1 ) - n ⋅ q = 1.$ (7)

Consider the following equivalences in mod p:
$( ( |{ 5p- 1 ≡ 2p-1 |{ 5n(p-1) ≡ 2n(p-1) ⇒ |( 5q ≡ 2q |( 5mq ≡ 2mq$ which yields $n(p-1) mq n(p- 1) mq 5 .2 ≡ 2 .5 ,$ which, combining with (7), implies that 5 ≡ 2 (mod p) and therefore p = 3 (rejected since we are assuming p > 5).

In conclusion, all possible values of (p,q) are (3, 3); (3, 13); (13, 3). __

Solution. First note that for any x ∈ ℤ, gcd(x - 1,x + 1) = gcd(2,x + 1) ≤ 2.
WLOG assume p ≥ q. If p = q then p²∣2^p+1 ⇒ p = q = 2. If p > q:

If q = 2 then 2p∣2² + 2^p or p∣2 + 2^p-1 so p ∈{2, 3}.

If q > 2, we have q∣2^p + 2^q = 2^q(2^p-1 + 1) so

q | 2p+1 - 1 ⇒ 22(p-q) ≡ 1 (mod p).

(8)

Let a be the smallest positive integer satisfying 2^a ≡ 1 (mod q) (i.e., a is the order of 2 in ℤ_q). By the property of order,

a | q - 1 and a | 2 (p - q).

Let p-q = 2^k ⋅m,q - 1 = 2^l ⋅n,a = 2^r ⋅s where k + 1 ≥ r,l ≥ r,s∣m,s∣n and m,n,s are odd. Consider two cases:

If r = k + 1 then l ≥ k + 1, so

2(p - q)	= 2^k+1 ⋅ m,
q - 1	= 2^l ⋅ n

would imply

2(p - q)s	= am
(q - 1)m	= (p - q) ⋅ n ⋅ 2^l-k-1.

It then follows that

n ⋅-2l-k--1 (q --1) ⋅ m q --1 2l ⋅-n 2s = 2s(p - q) = a = 2r ⋅ s,

which results in

2l-k- 2 = 2l-r ⇒ r = k + 2,

which is false. Hence this case does not yield any solution.

If r ≤ k then
$a p- q a | p - q ⇒ q | 2 - 1 | 2 - 1.$ (9)

From (8) and (9) we see that q∣(2^p-q - 1, 2^p-q + 1). On the other hand, gcd(2^p-q - 1, 2^p-q + 1) ≤ 2 as remarked earlier, so it follows that q = 2. However, this is false since we are assuming q > 2.

In conclusion, all values of (p,q) are (2, 2); (2; 3), (3; 2).

Solution. Let S = {(x,y,z)∣(xy + 1)(yz + 1)(zx + 1) is square}. Consider the tuple (x,y,z) ∈ S where x + y + z is smallest. WLOG assume z = max{x,y,z}.
Let t be a root of the equation.

t2 + x2 + y2 + z2 - 2(xy + yz + zt + tx + zx + ty) - 4xyzt - 4 = 0.

which is equivalent to

2 2 2 2 t - 2t(x + y + z + 2xyz ) + x + y + z - 2(xy + yz + zx ) - 4 = 0.

(10)

Note that (10) is equivalent to the following three equations:

	(x + y - z - t)² = 4(xy + 1)(zt + 1)	(11)
	(x + z - y - t)² = 4(xz + 1)(yt + 1)	(12)
	(x + t - y - z)² = 4(xt + 1)(yz + 1)	(13)

and that t ∈ ℤ because (10) has two integer solutions

∘ ------------------------- t1,2 = x + y + z + 2xyz ± 2 (xy + 1)(yz + 1)(zx + 1).

Multiplying the LHSs and RHSs of (11), (12), (13) together yields

	[(x + y + z - t)(x + z - y - t)(x + t - y - z)]²
=	[8(xy + 1)(yz + 1)(zx + 1)]² ⋅ [(xt + 1)(yt + 1)(zt + 1)],

so (xt + 1)(yt + 1)(zt + 1) is a square. We also have xt + 1,yt + 1,zt + 1 ≥ 0 and max{x,y,z} > 1 because x = y = z = 1 isn’t valid. Hence

t > ------1------> - 1. max {x,y,z }

Now consider two cases:

If t = 0 then (10) yields $2 2 (x + y + z) = 4(xy + yz + zx + 1) ⇔ (x + y - z) = 4(xy + 1 )$ so xy + 1 is a square. By similar arguments, yz + 1 and zx + 1 are also squares.

If t > 0 then (x,y,t) ∈ S. By the definition of (x,y,z), we see that t ≥ z, so t₁ ≥ z and t₂ ≥ z. On the other hand, we have

t₁t₂	= x² + y² + z² - 2(xy + yz + zx) - 4
	≤ z² - x(2z - x) - y(2z - y)
	< z²,

which is false. Hence this case does cannot happen.

In conclusion, each of xy + 1,yz + 1 and zx + 1 is a square. __

Solution. WLOG assume a ≤ b ≤ c. As 91 is not a square, we have a,b,c≠0.
If a ≥ 0 and b,c ≥ 0 so a² - bc < 0 < 91, which is false. Hence a < 0.
Also observe that if (a,b,c) satisfies the system of equations then so does (-a,-b,-c). Hence we only need to consider the tuples (a,b,c) where c > 0.
Now if b = c then

2 2 2 2 2 a - b = 91 = b - ab ⇒ a + ab - 2b = (a - b)(a + 2b) = 0

which implies either a = b or a = -2b. If a = b then a = b = c so a² - bc = 0, which is false. If a = -2b then 5b² = 91, which is also false. Hence it must be the case that b≠c. By similar arguments, a≠b. Now consider two cases:

If b > 0, then we have $2 2 91b = b(b - ac), 91c = c(c - ab) 3 3 ⇒ 91b - 91c = b - c 2 2 2 ⇒ 91 = b + bc + c ≥ 3b ⇒ b ∈ {1; 2;3;4;5}.$ From b it’s easy to find a and c. The solutions this case yields are (-10, 1, 9) and (-11, 5, 6).
If b < 0 then $91b = b(b2 - ac), 91a = a(a2 - bc) ⇒ 91 (b - a) = b3 - a3 ⇒ 91 = a2 + ab + b2 ≥ 3b2 ⇒ b ∈ {- 1;- 2;- 3;- 4;- 5}.$ The solutions this case yields are (-9; -1; 10) and (-6; -5; 11).

In conclusion, all possible values of (a,b,c) are (-10, 1, 9), (10,-1,-9), (-11, 5, 6), (11,-5,-6), (-9,-1, 10), (9, 1,-10), (-6,-5, 11), and their permutations. __

ab + a′b′	≡ 1 (mod 15)
bc + b′c′	≡ 1 (mod 15)
ca + c′a′	≡ 1 (mod 15)