Waste less time on Facebook — follow Brilliant.
×

RMO problem

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

Note by Sameer Pimparkhede
1 year, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 1 year, 10 months ago

Log in to reply

\(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 · 1 year, 10 months ago

Log in to reply

@Mathh Mathh Have you verified \(19^{93} - 13^{99} > 162\)? Jake Lai · 1 year, 10 months ago

Log in to reply

@Jake Lai Proving \(19^{93}>13^{99}\) is enough. I've edited the answer, didn't notice I had to prove it was positive. Mathh Mathh · 1 year, 10 months ago

Log in to reply

@Mathh Mathh True, my mind shut off for a second. Jake Lai · 1 year, 10 months ago

Log in to reply

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 · 1 year, 10 months ago

Log in to reply

@Jake Lai @Daniel Liu I put that theorem to good use :3 Jake Lai · 1 year, 10 months ago

Log in to reply

@Jake Lai I don't think you used it correctly. Where is the quadratic term? Daniel Liu · 1 year, 10 months ago

Log in to reply

@Daniel Liu What theorem is being referred to? Mathh Mathh · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

@Daniel Liu Trivially 0 is a quadratic residue modulo anything. The more I think about it the wronger it's becoming actually ;-; Jake Lai · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...