2

I'm having some issues solving the following example -

For any positive integer, prove that:

$a^3 \equiv x \space mod \space 9$

where $x = \{0, 1, 8\}$

What I usually do with such examples is attempt and apply mathematical induction and create a gather solution in that way. My approach was something as follows:

  1. $a = 0$ then $0^3 \equiv x \space mod \space$ $(true)$
  2. $a' = a + 1$ then $a^3 + 3a^2 + 3a + 1 \equiv x \space mod \space 9$

therefore,

  1. $(x' \space mod \space 9) \space + a^3 + 3a^2 + 3a + 1 \equiv x \space mod \space 9$

However as the x itself is a set, it does not necessarily have equality in the upper equation (3rd), even though x, and x' consist of same elements in this case (from same set), elements are shifted by +1. Is there any way of proving equivalence with this method or do I need to resort to another one.

If so, what would be the most optimal way of searching for a solution in this case ?

Thank you

Bill Dubuque
  • 272,048
Stefan
  • 69
  • You don't mean $x={0,1,8}$, but rather $x\in{0,1,8}$ – saulspatz Aug 24 '19 at 00:52
  • The easiest solution is to test 9 cases, for x from 0 to 8, but there isn't a much faster way to find the set of x for such a small modular base. – Gabe Aug 24 '19 at 01:11
  • @saulspatz If being pedantic then $,x\in {0,1,8},$ doesn't work because it is $\ x\equiv 0,1,8,,$ not $,x=0,1,8.,$ But there is much abuse of notation around such. – Bill Dubuque Aug 24 '19 at 01:42
  • @BillDubuque I'm not trying to be pedantic. I was trying to respond to the OP's apparent confusion when he said "because $x$ itself is a set." I also don't appreciate the personal attack. Learn some manners! – saulspatz Aug 24 '19 at 02:01
  • @saulspatz I see no "personal attacks". No one claimed you were being (overly) pedantic (nor is there anything wrong with being pedantic - esp. in math where precision is crucial). Chill out. – Bill Dubuque Aug 24 '19 at 02:04

4 Answers4

4

Note that $(a+3)^3 = a^3 + 9 a^2 + 27 a + 27 \equiv a^3 \bmod 9$. Therefore, it's enough to consider $a\in\{0,1,2\}$, in which case it's clear that $a^3 \in \{0,1,8\}$.

More generally, the same argument gives $\{a^p \bmod p^2 : a \in \mathbb Z \} = \{a^p \bmod p^2 : a = 0, \dots, p-1\} $. The key point is the binomial expansion of $(a+p)^p$: all coefficients but the first are multiples of $p^2$.

lhf
  • 216,483
3

You don't want to do induction here.

As an alternative you may consider $a$ in $\mod 3$.
That is, consider $3$ cases: $a = 3k,3k+1, 3k+2$,
and in each case look at the remainder $a^3\mod 9$.

AgentS
  • 12,195
3

By below: $\ \overbrace{a\equiv 0,\pm1\pmod{\!3}}^{\rm Division\ Algorithm}\,\Rightarrow\,a^{\large 3}\equiv [0,\pm1]^{\large 3}\equiv 0,\pm1\pmod{\!3^{\large 2}}$

Lemma $\,\ \ \ a\ \equiv\ b\ \ \pmod{ n}\ \Rightarrow\ a^{\large n}\, \equiv\ b^{\large n}\ \pmod{\!n^{\large 2}}$

Proof $\ $ By hypothesis $\ a = b\!+\!nj\,$ for some integer $\,j\,$ so by the Binomial Theorem $$ a^{\large n} = (b\!+\!nj)^{\large n}\! = b^{\large n}\! + \color{#c00}n(\color{#c00}nj)\, b^{\large n-1}\! + (\color{#c00}nj)^{\large\color{#c00} 2}(\cdots) \equiv b^{\large n}\!\! \pmod{\!\color{#c00}{n^{\large 2}}}\qquad\qquad$$

Remark $ $ It is worth the slight extra effort to prove the general lemma above (vs. OP special case) since it often proves handy in number theory.

Bill Dubuque
  • 272,048
  • We used $\ 2\equiv -1 \pmod{!3}\ $ since $,-1,$ is simpler to power - like using $,9\equiv -1\pmod{!10},$ in casting out nines. – Bill Dubuque Aug 24 '19 at 02:15
2

In addition to ganeshie8's answer, you can instead consider the cases $3k-1$, $3k$ and $3k+1$. Then using the binomial theorem, it is obvious that this evaluates to $-1$, $0$ and $1$ modulo $3$.

Toby Mak
  • 16,827