0

In the book, Elements of programming CASE ANALYSIS has been listed as one of the approaches to solve a problem.

As an example, the book states that

for all n , n^3 mod 9 would either be 0,1,8 and even splits this problem into following cases where n belongs to the following category

  1. n = 3m
  2. n = 3m + 1
  3. n = 3m +2

Based on the way that this has been glossed over in the book, it seems like a trivial concept. But i couldn't establish the relation between n^3 and all the three cases which are listed above. They seems to be (at least to my understanding) the numbers which are similar to n = num mod 3

But how does it relate to proving n^3 mod 9 is 0,1 and 8 and how these three cases would suffice to prove the problem statement

venkat
  • 3

3 Answers3

1

You only need to cube each one: \begin{align} (3m+k)^3 &= 27m^3 + 27m^2k + 9mk^2 + k^3 \\ &= 9 (3m^3 +3m^2k+mk^2)+k^3 \end{align} You can now see that $(3m+k)^3 \equiv k^3 \text{ mod }9 $. So when $k=0,1,2$ you find every cube is $0,1 \text{ or }8 \text{ mod } 9$.

Added: Every whole number is of the form $3m+k$ for some $m, k$ and where $k=0,1$ or $2$.

WA Don
  • 4,488
  • yeah now this makes much more sense. so does this mean all the numbers could be represented by 3m+ k ? – venkat Jun 13 '20 at 08:25
  • Yes, all whole numbers must be of the form $3m+k$ for $k=0,1$ or $2$. Just think of the remainder when you divide by 3: there are only three possibilities. – WA Don Jun 13 '20 at 09:03
0

$1^3\equiv1(\mod 9)$

$2^3\equiv8(\mod 9)$

$3^3\equiv0(\mod 9)$

$4^3\equiv1(\mod 9)$

$5^3\equiv8(\mod 9)$

$6^3\equiv0(\mod 9)$

Do you see the pattern?

Lee
  • 1,910
  • 12
  • 19
0

Let $n$ be a natural number. Then $n$ can be of the form: $n=3k, n=3k+1,n=3k+2$. Those are the only three options for $n$, either it's divisible by 3,has a remainder 1 or a remainder 2.

So suppose $n=3k$. then $n^3 = (3k)^3= 27k^3=0 (mod 9)$ In that case, $n^3$ is 0 (mod 9).

Now suppose, $n=3k+1$. then $n^3 = (3k+1)^3= 27 k^3 + 27 k^2 + 9 k + 1=1 (mod 9)$ In that case, $n^3$ is 1 (mod 9).

And finally, suppose $n=3k+2$. then $n^3 = (3k+2)^3=27 k^3 + 54 k^2 + 36 k + 8=8 (mod 9)$ In that case, $n^3$ is 8 (mod 9). And since we did all the cases, the mod 9 of a cube is either 0, 1 or 8. Hope this helps!

Chill
  • 36