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

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.

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

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

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.

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

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

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

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

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

Yea butLog in to reply

$k$ is a

Your statement of the theorem was incorrect there: "non-zeroquadratic residue mod $p$ iff $k$ is anon-zeroquadratic residue mod $p^n$ for someoddprime $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.

Log in to reply

Log in to reply

Wikipedia article. Can you inform me of the name?

I'm not sure what the name was, but it is in this part of aLog in to reply

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

Log in to reply