RMO problem

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

Note by Sameer Pimparkhede
4 years, 3 months ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 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"
MathAppears 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}$

Sort by:

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}$.

- 4 years, 3 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}$

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

True, my mind shut off for a second.

- 4 years, 3 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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

What theorem is being referred to?

- 4 years, 3 months ago

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?

- 4 years, 3 months ago

"$((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, 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.

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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.

- 4 years, 3 months ago

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.

- 4 years, 3 months ago