# Math Help - Show that (3k + 1)^9 ≡ 1 (mod 27)

1. ## Show that (3k + 1)^9 ≡ 1 (mod 27)

I know that 1 (mod 27) ≡ K implies that K = 27a + 1 where a is an integer.

Thus I must show that (3k+1)^9 can turn out in that way. But the power is 9, that's a lot!!! Isn't there an easier way to show this?

2. ## Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

Originally Posted by SweatingBear
I know that 1 (mod 27) ≡ K implies that K = 27a + 1 where a is an integer.

Thus I must show that (3k+1)^9 can turn out in that way. But the power is 9, that's a lot!!! Isn't there an easier way to show this?
Here's how I think the best way to go about this is. Note that $(3k+1,27)=1$ and so by Euler's theorem this implies that $(3k+1)^{\varphi(27)}=(3k+1)^{18}\equiv1\text{ mod }27$. This tells us that $x^2=1\text{ mod }27$ where $x=(3k+1)^{9}$. From this we may conclude that $(3k+1)^9\equiv \pm a\text{ mod }27$. Now, why is $(3k+1)^9\not\equiv-1\text{ mod }27$?

3. ## Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

another way is to use the binomial theorem...now, i know what you're thinking...that's a lot of calculation, but:

every term is going to be of the form a(3k)^n. all the terms for n > 2 are going to disappear since (3k)^3 = (27)(k^3) = 0 (mod 27).

so that leaves just the 9k^2, 3k and constant term.

the constant term is going to be 1^9 = 1.

the coefficient of the 3k term is going to be 9, and 9(3k) = 27k = 0 (mod 27).

the coefficient of the (3k)^2 term is going to be 9!/(2!7!) = (8)(9)/2 = 36, and (36)(3k)^2 = (27)(4k^2) = 0 (mod 27),

so only the constant term survives, and that's 1.

4. ## Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

Originally Posted by Deveno
another way is to use the binomial theorem...now, i know what you're thinking...that's a lot of calculation, but:

every term is going to be of the form a(3k)^n. all the terms for n > 2 are going to disappear since (3k)^3 = (27)(k^3) = 0 (mod 27).

so that leaves just the 9k^2, 3k and constant term.

the constant term is going to be 1^9 = 1.

the coefficient of the 3k term is going to be 9, and 9(3k) = 27k = 0 (mod 27).

the coefficient of the (3k)^2 term is going to be 9!/(2!7!) = (8)(9)/2 = 36, and (36)(3k)^2 = (27)(4k^2) = 0 (mod 27),

so only the constant term survives, and that's 1.
Starting to make a bit more sense, but the assumptions that you are making or evincing are not as obvious to me as they are to you. Could you please explain the middle steps a bit more thoroughly? Thank you for clearing things up!!

5. ## Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

Originally Posted by SweatingBear
Starting to make a bit more sense, but the assumptions that you are making or evincing are not as obvious to me as they are to you. Could you please explain the middle steps a bit more thoroughly? Thank you for clearing things up!!
The binomial theorem is $(1+\phi)^n = \sum_{k=0}^n {n \choose k}\phi^k$

In your case $\phi = 3x$

$(1+3x)^9 =$

$1 + {9 \choose 1}(3x)^1 + {9 \choose 2}(3x)^2 + {9 \choose 3}(3x)^3 + {9 \choose 4}(3x)^4 + {9 \choose 5}(3x)^5 +{9 \choose 6}(3x)^6$
$+ {9 \choose 7}(3x)^7+ {9 \choose 8}(3x)^8 + (3x)^9$

Also note that $a^b = a^{c+d} = a^ca^d$ given that $b = c+d$

In our case take note that for each term above ${9 \choose 2}(3x)^2$ the exponent can be expressed as

${9 \choose k}(3x)^{3+k}$ which, due to the law of exponents is the same as ${9 \choose k}(3x)^3(3x)^k$ (where k is a non-negative integer)

We also know from our laws of exponents that $(3x)^3 = 27x^3$ and so each term which has a $(3x)^n$ term where $n \geq 3$ will be a multiple of 27.

If a number is a multiple of 27 then it is $0(\mod 27)$

This means that each term above ${9 \choose 2}(3x)^2$ will be $0(\mod 27)$ (because they're all multiples of 27) and we're simply adding 0 after the third term.

Therefore we look at our first two terms $1 + {9 \choose 1}(3x)^1 + {9 \choose 2}(3x)^2 = 1 + 9(3x) + 36(9x^2) = 1 + 27x + 324x^2$

You can then take those terms to mod 27 and be left with the constant. Does that make more sense?

, mod