RMO problem

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

Note by Sameer Pimparkhede
4 years, 1 month ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

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

(18+1)931+(931)181+12×1855(mod81) {\left(18+1\right)}^{93}\equiv1+\binom{93}{1}18 \equiv1+12\times18\equiv55\pmod{81}.

Now do the same for 13:

(12+1)991+(991)121+12×1855(mod81) {\left(12+1\right)}^{99}\equiv1+\binom{99}{1}12 \equiv1+12\times18\equiv55\pmod{81}.

So they are equivalent mod 162!

Now 1993>139919^{93}>13^{99} because 192132>21990>(1390)(245)\frac{19^2}{13^2}>2 \Rightarrow 19^{90}>(13^{90})(2^{45}). Trivially 139<24513^9<2^{45} as 13<2513<2^5 thus 1990>139919^{90}>13^{99}.

Dylan Pentland - 4 years, 1 month ago

Log in to reply

162=234162=2\cdot 3^4. Obviously 1993139919^{93}-13^{99} is even, so our task is to prove 199313990(mod ⁣34)19^{93}-13^{99}\equiv 0\,\pmod{\! 3^4}.

Use Binomial theorem, note 182+k0,124+k0(mod ⁣34)18^{2+k}\equiv 0,\, 12^{4+k}\equiv 0\pmod{\! 3^4} for k0k\ge 0. Binomial theorem is often useful when finding aba^b mod pkp^k with k2k\ge 2, especially when a=pk±1a=pk\pm 1 (as in this case), even more so when a=pnk±1a=p^nk\pm 1 for some n2n\ge 2.

19931399(1+18)93(1+12)9919^{93}-13^{99}\equiv (1+18)^{93}-(1+12)^{99}

1+(931)181(991)12(992)122(993)123(mod ⁣34)\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 (992)122(993)1230(mod ⁣34)\binom{99}{2}12^2\equiv \binom{99}{3}12^3\equiv 0\pmod{\! 3^4}, so

1+(12)181(18)120(mod ⁣34)\equiv 1+(12)18-1-(18)12\equiv 0\pmod{\! 3^4}

We're left with proving 1993>139919^{93}>13^{99}.

(192)46.5>(2132)46.5>(24)61393>1361393=1399(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 - 4 years, 1 month ago

Log in to reply

Have you verified 19931399>16219^{93} - 13^{99} > 162?

Jake Lai - 4 years, 1 month ago

Log in to reply

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

mathh mathh - 4 years, 1 month ago

Log in to reply

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

Jake Lai - 4 years, 1 month ago

Log in to reply

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

We have that an integer kk is a quadratic residue modulo pp iff it is a quadratic residue modulo pnp^{n} for pp some prime and nn a positive integer. Since 199313991931990(mod3)19^{93} - 13^{99} \equiv 1^{93} - 1^{99} \equiv 0 \pmod{3}, then trivially 1993139919^{93} - 13^{99} is divisible by 343^{4}.

And we're done.

Or are we?


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

Because

19931399=1136(1+613)93e93×6/13136>242136=(12813)6>96>>1+ϵ\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 19931399>96×1399>>>16219^{93} - 13^{99} > 9^{6} \times 13^{99} >>> 162 :D

Jake Lai - 4 years, 1 month ago

Log in to reply

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

Jake Lai - 4 years, 1 month ago

Log in to reply

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

Daniel Liu - 4 years, 1 month 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 - 4 years, 1 month ago

Log in to reply

@Jake Lai Yea but 1993139919^{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 - 4 years, 1 month ago

Log in to reply

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

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

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

mathh mathh - 4 years, 1 month ago

Log in to reply

@Daniel Liu What theorem is being referred to?

mathh mathh - 4 years, 1 month 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 - 4 years, 1 month ago

Log in to reply

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

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

Ak2(mod ⁣pn)Ak2(mod ⁣pm)\,A\equiv k^2\pmod{\! p^n}\,\Rightarrow\, A\equiv k^2\,\pmod{\! p^m}, so (Apn)=1(Apm)=1\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:

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

Ak2(mod ⁣pm)A((A+k2)(2k)1)2(mod ⁣p2m)A\equiv k^2\pmod{\! p^m}\,\Rightarrow\, A\equiv \left((A+k^2)(2k)^{-1}\right)^2\pmod{\! p^{2m}}

Then 1=(Apm)=(Ap2m)=(Ap4m)=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 nn. From the first direction the result follows.

Using Hensel's lemma: let f(x)=x2Af(x)=x^2-A. Since exists rr such that f(r)0(mod ⁣pm)f(r)\equiv 0\pmod{\! p^m} (by definition of (Apm)=1\left(\frac{A}{p^m}\right)=1) and f(r)2r≢0(mod ⁣p)f'(r)\equiv 2r\not\equiv 0\pmod{\! p}, then exists ss such that f(s)0(mod ⁣pm+c)f(s)\equiv 0\pmod{\! p^{m+c}} for any 1cm1\le c\le m (i.e. (Apm+c)=1\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 - 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...