RMO problem

Prove that $19^{93}-13^{99}$ is a positive integer divisible by 162

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Observe that $162=81\times2$ so we need to have $19^{93}\equiv13^{99}$ in mod 2 and mod 81.

Mod 2 is easy - $19^{93}\equiv13^{99}\equiv1 \pmod{2}$ . Now let's find each separately in mod 81:

${\left(18+1\right)}^{93}\equiv1+\binom{93}{1}18 \equiv1+12\times18\equiv55\pmod{81}$ .

Now do the same for 13:

${\left(12+1\right)}^{99}\equiv1+\binom{99}{1}12 \equiv1+12\times18\equiv55\pmod{81}$ .

So they are equivalent mod 162!

Now $19^{93}>13^{99}$ because $\frac{19^2}{13^2}>2 \Rightarrow 19^{90}>(13^{90})(2^{45})$ . Trivially $13^9<2^{45}$ as $13<2^5$ thus $19^{90}>13^{99}$ .

Dylan Pentland - 5 years, 11 months ago

$162=2\cdot 3^4$ . Obviously $19^{93}-13^{99}$ is even, so our task is to prove $19^{93}-13^{99}\equiv 0\,\pmod{\! 3^4}$ .

Use Binomial theorem, note $18^{2+k}\equiv 0,\, 12^{4+k}\equiv 0\pmod{\! 3^4}$ for $k\ge 0$ . Binomial theorem is often useful when finding $a^b$ mod $p^k$ with $k\ge 2$ , especially when $a=pk\pm 1$ (as in this case), even more so when $a=p^nk\pm 1$ for some $n\ge 2$ .

$19^{93}-13^{99}\equiv (1+18)^{93}-(1+12)^{99}$

$\equiv 1+\binom{93}{1} 18 -1-\binom{99}{1} 12-\binom{99}{2}12^2-\binom{99}{3}12^3\pmod{\! 3^4}$

Clearly $\binom{99}{2}12^2\equiv \binom{99}{3}12^3\equiv 0\pmod{\! 3^4}$ , so

$\equiv 1+(12)18-1-(18)12\equiv 0\pmod{\! 3^4}$

We're left with proving $19^{93}>13^{99}$ .

$(19^{2})^{46.5}> (2\cdot 13^2)^{46.5}>(2^{4})^{6}\cdot 13^{93}>13^6\cdot 13^{93}=13^{99}$

mathh mathh - 5 years, 11 months ago

Have you verified $19^{93} - 13^{99} > 162$ ?

Jake Lai - 5 years, 11 months ago

Proving $19^{93}>13^{99}$ is enough. I've edited the answer, didn't notice I had to prove it was positive.

mathh mathh - 5 years, 11 months ago

@Mathh Mathh – True, my mind shut off for a second.

Jake Lai - 5 years, 11 months ago

Let's examine the prime factorization of $162$ . It's $2 \times 3^{4}$ . Clearly, $19^{93} - 13^{99}$ is the difference of two odd numbers so it is surely divisible by $2$ .

We have that an integer $k$ is a quadratic residue modulo $p$ iff it is a quadratic residue modulo $p^{n}$ for $p$ some prime and $n$ a positive integer. Since $19^{93} - 13^{99} \equiv 1^{93} - 1^{99} \equiv 0 \pmod{3}$ , then trivially $19^{93} - 13^{99}$ is divisible by $3^{4}$ .

And we're done.

Or are we?

However, we have yet to verify that $19^{93} - 13^{99} > 162$ . If we can show that $\frac{19^{93}}{13^{99}} > 1+\epsilon$ - and thus the difference $> 13^{99}\epsilon > 162$ - victory is ours for the taking.

Because

$\frac{19^{93}}{13^{99}} = \frac{1}{13^{6}}\left(1+\frac{6}{13}\right)^{93} \approx \frac{e^{93 \times 6 / 13}}{13^{6}} > \frac{2^{42}}{13^{6}} = \left( \frac{128}{13}\right) ^{6} > 9^{6} >> 1+\epsilon$

we hence have $19^{93} - 13^{99} > 9^{6} \times 13^{99} >>> 162$ :D

Jake Lai - 5 years, 11 months ago

@Daniel Liu I put that theorem to good use :3

Jake Lai - 5 years, 11 months ago

I don't think you used it correctly. Where is the quadratic term?

Daniel Liu - 5 years, 11 months ago

@Daniel Liu – Trivially 0 is a quadratic residue modulo anything. The more I think about it the wronger it's becoming actually ;-;

Jake Lai - 5 years, 11 months ago

@Jake Lai – Yea but $19^{93}-13^{99}$ is not a square. Even if it was, you can't say anything about the thing being squared anyways, just the quadratic residues.

Daniel Liu - 5 years, 11 months ago

@Jake Lai – Your statement of the theorem was incorrect there: " $k$ is a non-zero quadratic residue mod $p$ iff $k$ is a non-zero quadratic residue mod $p^n$ for some odd prime $p$ and a positive integer $n$ ".

Even if you were correct with the statement (very hypothetical - it's incorrect, because e.g. $3\equiv 0^2\pmod{\! 3}$ , but $3$ is not a quadratic residue mod $9$ ), it would tell you exactly that $19^{93}-13^{99}\equiv i^2\pmod{\! 3^4}$ for some $i\in\Bbb Z_{3^4}$ , but the statement doesn't tell you $i^2$ has to be equivalent to $0$ mod $3^4$ .

If you think about it more, you can see your understanding would show $19^{93}-13^{99}$ is divisible by arbitrarily large powers of $3$ , so is as well divisible by $3^{99!}$ , etc.

mathh mathh - 5 years, 11 months ago

@Daniel Liu – What theorem is being referred to?

mathh mathh - 5 years, 11 months ago

@Mathh Mathh – I'm not sure what the name was, but it is in this part of a Wikipedia article. Can you inform me of the name?

Daniel Liu - 5 years, 11 months ago

@Daniel Liu – " $((A,p)=1,\, p$ odd prime $) \,\,\Rightarrow \, (\left(\frac{A}{p^m}\right)=1\iff \left(\frac{A}{p^n}\right)=1\,$ for arbitrary $n,m\ge 1)$ ".

It's a consequence of Hensel's Lemma. If wlog $m<n$ , one direction is simple:

$\,A\equiv k^2\pmod{\! p^n}\,\Rightarrow\, A\equiv k^2\,\pmod{\! p^m}$ , so $\left(\frac{A}{p^n}\right)=1\,\Rightarrow\, \left(\frac{A}{p^m}\right)=1$

The other direction can either be proven using Hensel's lemma or elementarily:

$(A-k^2)^2=(A+k^2)^2-A(2k)^2$ , so since $(2k,p)=1$ :

$A\equiv k^2\pmod{\! p^m}\,\Rightarrow\, A\equiv \left((A+k^2)(2k)^{-1}\right)^2\pmod{\! p^{2m}}$

Then $1=\left(\frac{A}{p^m}\right)=\left(\frac{A}{p^{2m}}\right)=\left(\frac{A}{p^{4m}}\right)=\cdots$ until the degree is larger than $n$ . From the first direction the result follows.

Using Hensel's lemma: let $f(x)=x^2-A$ . Since exists $r$ such that $f(r)\equiv 0\pmod{\! p^m}$ (by definition of $\left(\frac{A}{p^m}\right)=1$ ) and $f'(r)\equiv 2r\not\equiv 0\pmod{\! p}$ , then exists $s$ such that $f(s)\equiv 0\pmod{\! p^{m+c}}$ for any $1\le c\le m$ (i.e. $\left(\frac{A}{p^{m+c}}\right)=1$ ). Repeatedly apply this, then apply the first direction. I'm not aware of any name for this exact lemma.

mathh mathh - 5 years, 11 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$