RMO problem

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

Note by Sameer Pimparkhede
3 years, 3 months ago

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

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

- 3 years, 3 months ago

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

- 3 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.

- 3 years, 3 months ago

True, my mind shut off for a second.

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

- 3 years, 3 months ago

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

- 3 years, 3 months ago

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

- 3 years, 3 months ago

What theorem is being referred to?

- 3 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?

- 3 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<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.

- 3 years, 3 months ago

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

- 3 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.

- 3 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.

- 3 years, 3 months ago