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.

Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold

- bulleted - list

bulleted

list

1. numbered 2. list

numbered

list

Note: you must add a full line of space before and after lists for them to show up correctly

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

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.

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

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

Easy Math Editor

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:

`*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`\(`

...`\)`

or`\[`

...`\]`

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

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

Log 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

$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