 How Cheenta works to ensure student success?
Explore the Back-Story

# RMO 2018 Tamil Nadu Problem 3 - Nonlinear Diophantine Equation RMO 2018 Tamil Nadu Problem 3 is from Number Theory. We present sequential hints for this problem. Do not read all hints at one go. Try it yourself.

# Problem

Show that there are infinitely many 4-tuples (a, b, c, d) of natural numbers such that $a^3 + b^4 + c^5 = d^7$.

## Key ideas you will need to solve this problem

• Number Theory:
• Understand the notion of modular inverse.
• Bezout's Theorem.

Also see

## Hint 1: Powers of 3

Powers of 3 have a very interesting property: $$3^n + 3^n + 3^n = 3^{n+1}$$

This simple observation is the key to this problem.

## Hint 2: Expressing $3^n$ in multiple ways.

We want $a^3 = 3^n, b^4 = 3^n, c^5 = 3^n$. Clearly n needs to be a multiple of 3, 4 and 5. For example, $3 \times 4 \times 5 = 60$ may work. That is $$3^{60} + 3^{60} + 3^{60} = (3^{20})^3 + (3^{15})^4 + (3^{12})^5$$

Hence in this case $$a = 3^{20}, b = 3^{15}, c = 3^{12}$$

This will work for any multiple of 60. Suppose 60k is a multiple of 60 (that is k is any integer). Then we will have $$a = 3^{20k}, b = 3^{15k}, c = 3^{12k}$$

## Hint 3: We need 60k +1 to be a multiple of 7

Notice that $$3^{60k} + 3^{60k} + 3^{60k} = (3^{20k})^3 + (3^{15k})^4 + (3^{12k})^5 = 3^{60k+1}$$

We need $$3^{60k+1} = d^7$$

That is 60k +1 needs to be a multiple of 7. In terms of modular arithmetic we want $$60k + 1 \equiv 0 \mod 7$$

$60 \equiv 4 \mod 7 \ \Rightarrow 60k + 1 \equiv 4k +1 \mod 7 \ \Rightarrow 4k \equiv - 1 \equiv 6 \mod 7$

This is where we will use the notion of inverse of a number modulo 7. Inverse of 4 modulo 7 is 2. This is because $4 \times 2 = 8 \equiv 1 \mod 7$. The Bezout's theorem guarantees existence of inverse of 4 modulo 7. (Look into the reference at the end of this discussion if you do not know these ideas).

$4k \equiv 6 \mod 7 \ \Rightarrow 2\times 4k \equiv 2\times 6 \mod 7 \ \Rightarrow k \equiv 5 mod 7$

Hence k = 7k' + 5 is suitable for our purpose.

Since there are infinitely many such integers with have infinitely many 4 tuples that will work.

Illustration: For k' = 0, k = 5. Therefore $60 \times 5 = 300$ should work. And it does: $$3^{300} + 3^{300} + 3^{300} = (3^{100})^3 + (3^{75})^4 + (3^{60})^5 = 3^{301} = (3^{43})^7$$

# Reference:

• These ideas are usually discussed in the Number Theory I module of Cheenta Math Olympiad Program.
• Elementary Number Theory by David Burton is a good reference for some these ideas.

Also see

RMO 2018 Tamil Nadu Problem 3 is from Number Theory. We present sequential hints for this problem. Do not read all hints at one go. Try it yourself.

# Problem

Show that there are infinitely many 4-tuples (a, b, c, d) of natural numbers such that $a^3 + b^4 + c^5 = d^7$.

## Key ideas you will need to solve this problem

• Number Theory:
• Understand the notion of modular inverse.
• Bezout's Theorem.

Also see

## Hint 1: Powers of 3

Powers of 3 have a very interesting property: $$3^n + 3^n + 3^n = 3^{n+1}$$

This simple observation is the key to this problem.

## Hint 2: Expressing $3^n$ in multiple ways.

We want $a^3 = 3^n, b^4 = 3^n, c^5 = 3^n$. Clearly n needs to be a multiple of 3, 4 and 5. For example, $3 \times 4 \times 5 = 60$ may work. That is $$3^{60} + 3^{60} + 3^{60} = (3^{20})^3 + (3^{15})^4 + (3^{12})^5$$

Hence in this case $$a = 3^{20}, b = 3^{15}, c = 3^{12}$$

This will work for any multiple of 60. Suppose 60k is a multiple of 60 (that is k is any integer). Then we will have $$a = 3^{20k}, b = 3^{15k}, c = 3^{12k}$$

## Hint 3: We need 60k +1 to be a multiple of 7

Notice that $$3^{60k} + 3^{60k} + 3^{60k} = (3^{20k})^3 + (3^{15k})^4 + (3^{12k})^5 = 3^{60k+1}$$

We need $$3^{60k+1} = d^7$$

That is 60k +1 needs to be a multiple of 7. In terms of modular arithmetic we want $$60k + 1 \equiv 0 \mod 7$$

$60 \equiv 4 \mod 7 \ \Rightarrow 60k + 1 \equiv 4k +1 \mod 7 \ \Rightarrow 4k \equiv - 1 \equiv 6 \mod 7$

This is where we will use the notion of inverse of a number modulo 7. Inverse of 4 modulo 7 is 2. This is because $4 \times 2 = 8 \equiv 1 \mod 7$. The Bezout's theorem guarantees existence of inverse of 4 modulo 7. (Look into the reference at the end of this discussion if you do not know these ideas).

$4k \equiv 6 \mod 7 \ \Rightarrow 2\times 4k \equiv 2\times 6 \mod 7 \ \Rightarrow k \equiv 5 mod 7$

Hence k = 7k' + 5 is suitable for our purpose.

Since there are infinitely many such integers with have infinitely many 4 tuples that will work.

Illustration: For k' = 0, k = 5. Therefore $60 \times 5 = 300$ should work. And it does: $$3^{300} + 3^{300} + 3^{300} = (3^{100})^3 + (3^{75})^4 + (3^{60})^5 = 3^{301} = (3^{43})^7$$

# Reference:

• These ideas are usually discussed in the Number Theory I module of Cheenta Math Olympiad Program.
• Elementary Number Theory by David Burton is a good reference for some these ideas.

Also see

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### Knowledge Partner  