2
$\begingroup$

This question is about the logic of a proof, not the number theory involved.

Exercise (4.1).9 of Number Theory Step by Step (Singh) is:

Find a solution of $x^{101} ≡ 5 \pmod {13}$.

The chapter introduces Fermat's Little Theorem, that if $p$ is prime and does not divide integer $a$, then $a^{p-1} \equiv 1 \pmod p$. The book says it like this (link).

The following is my solution (which matches the author's official solution too):

My Solution

If we assume [see Question below] the prime 13 does not divide $x$, then we have

$x^{12} \equiv 1 \pmod {13}$

$(x^{12})^{8} \equiv x^{96} \equiv 1 \pmod {13}$

And so

$x^{101} \equiv x^{96} \times x^{5} \equiv x^5 \equiv 5 \pmod {13}$

The following table shows some $x^5 \pmod{13}$.

x   x^5     x^5 mod 13

0   0       0
1   1       1
2   32      6
3   243     9
4   1024    10
5   3125    5  <--- solution
6   7776    2

We can see $x=5$ is a solution, and our assumption 13 does not divide $x=5$ holds.

Question

I am uncertain about assuming 13 does not divide $x$ at the start of the solution, in order to use Fermat's Little Theorem.

Typically, to use Fermat's Little Theorem, or any theorem, I have to show the preconditions hold first.

Here a solution emerges as $x=5$ which we confirm meets the theorem's preconditions, after we have found it.

The author's own solution (link to image) appears to ignore the theorem's requirement that prime $p$ must not divide $a$.

What am I missing?

$\endgroup$
2
  • 3
    $\begingroup$ I am not sure I understand your concern. You were asked to find a solution, and you found one. You were not asked to prove that this solution was unique. If you were, that would require showing that $0 \bmod{13}$ isn’t a solution, which is trivial. $\endgroup$ Commented 14 hours ago
  • $\begingroup$ To be precise, don't assume $13 \nmid x$. Prove it by contradiction. Assume toward a contradiction that there is a solution with $13 \mid x$. But then also $13 \mid x^{101}$, which means that $x^{101} \equiv 0 \neq 5 \pmod{13}$. That contradiction shows that our assumption that $13 \mid x$ has to be false. $\endgroup$ Commented 10 hours ago

2 Answers 2

Reset to default
4
$\begingroup$

The author (like many) is likely skipping the "degenerate" case (presumably obvious to the reader). Since you write in a comment that this is the first time you've encountered an argument like this, you may find it instructive to see how such arguments naturally generalize as below, e.g. inverting an algebraic number $\alpha$ by rationalizing the denominator of $\frac{1}{\alpha}$ (a method likely you have seen).

Generally, over any field (such as $\Bbb Z_p$) if a polynomial $f(x)$ has nonzero constant term $f(0)\neq 0$ then $x=0$ is not a root, so every root is nonzero, so invertible. Thus when doing algebra with roots of $f$ we can invert (and cancel) them. OP is the special binomial case $\,f(x) = x^n - a,\ a\!\neq\! 0$.

Generally the above shows that an $\rm\color{#c00}{algebraic}$ root of $f$ divides its simpler $\rm\color{#0a0}{integer}$ constant term, and this simpler multiple allows us to reduce $\rm\color{#c00}{algebraic}$ number inversion to $\rm\color{#0a0}{integer}$ inversion, e.g. using norms or rationalizing denominators.

You may also find instructive the case analysis in the comparison of the little Fermat Theorem in general vs. nonzero form: $\,a^p\equiv a\,$ vs. $\,a^{p-1}\equiv 1,\,$ a special case $\,f = x^{p-1}-1$ of

$$\begin{align} \forall x\!:&\ \ \ \ \ \ \ xf(x)= 0\\[.2em] \iff\ \forall x\ &\ [\:\!x\not= 0\Rightarrow f(x)= 0\:\!] \end{align}\qquad$$

$\endgroup$
1
  • 3
    $\begingroup$ @Downvoter If something is not clear please feel welcome to ask for elaboration. $\endgroup$ Commented 13 hours ago
4
$\begingroup$

Suppose $13\mid x$. Then $x\equiv 0\pmod{13}$. But then

$$x^{101}\equiv 0^{101}\pmod{13}=0\pmod{13},$$

a contradiction.

$\endgroup$
1
  • 1
    $\begingroup$ i.e. in $\,\Bbb Z_{13}\!:\ x = 0\,$ is clearly not a root of $\:\!f(x) = x^{101}-5\,$ since $\,f(0)= -5\neq 0.\,$ This argument is (implicitly) used in many places in algebra - as I explain in my answer. $\ \ $ $\endgroup$ Commented 12 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.