# Prove 11 does not divide $3^{3k-1}+5*3^k$ for any odd k.

First I did an induction proof that it does work for even k. Then I started the proof as so.

Suppose there exists a k of the form 2n+1, s.t 11 divides $3^{3k-1}+5*3^k$.

After some algebra I can arrive at this point $5*2^{6n-1}+3(2^{6n-1}+5*3^{2n})$

Since I proved separately this works for even k, the right side sum if of that form, $(2^{6n-1}+5*3^{2n})$ is divisible by 11. So I believe if I can somehow prove that 11 does not divide any power of 2, I would have finished the proof. However I don't know how to do that.

Someone may have to fix the tags as I'm not entirely sure what is appropriate here, sorry.

• "If I can somehow prove that $11$ does not divide any power of $2$." That should be immediate from the fact that $11$ is a prime number and the only primes appearing in $2^n$'s prime decomposition are twos. Remember that $p$ is a prime integer if and only if for all integers $a,b$ if $p\mid ab$ then $p\mid a$ or $p\mid b$. In this case if $11$ were to divide $2^n$ then since $11$ were prime it must divide $2$. – JMoravitz Nov 1 '17 at 23:40
• The phrase to search for is "The Fundamental Theorem of Arithmetic." As for the name for the property I described about primes... it is the very definition of what it means to be a prime. – JMoravitz Nov 1 '17 at 23:47
• It should be easier to look at $3^{k-1}+5\cdot 3^k=3^{k-1}(1+15)=3^{k-1}\cdot 2^4$, there is no $11$ in prime factorisation ... – rtybase Nov 1 '17 at 23:47
• Hint: $3^{3k-1}+5\cdot 3^k\equiv 4\cdot z\cdot (z^2+4)\pmod{11}$ at $z=3^k$.<br> $3^k$ never is a multiple of $11$ and $z^2+4$ is irreducible over $\mathbb{F}_{11}$ since $\left(\frac{-4}{11}\right)=\left(\frac{-1}{11}\right)=(-1)^5=-1.$ – Jack D'Aurizio Nov 2 '17 at 0:11

HINT

If $11|2^m$ for $m\in\mathbb{N}$ it would mean that $11|2$ which is a contradiction.

This follows from the fact that if a prime $p$ divides the product of $2$ numbers, say $p|ab$ then $p|a$ or $p|b$. Apply this to $a=2^{m-1}, b=2$.

So if all else is correct your proof is finished.

A general proof for $k$ even and odd.$$3^{3k-1}+5*3^k=3^k(3^{2k-1}+5)$$ for which if $11$ divides the expression then $11$ should divide $3^{2k-1}+5$. This is not possible because the subgroup generated by $3$ is equal to $\{3,9,5,4,1\}$ and the five possible sums give, respectively the classes $$8,3,10,9,6$$ any of them is equal to zero modulo $11$.

$3^{3k-1}+5\times 3^k=3^{k-1}(3^{2k}+15)=3^{k-1}(x^2+15)$ with $x=3^k$

Also $x^2+15\equiv x^2+4\pmod{11}$

$\begin{array}{l} k=0: & 3^0\equiv 1\pmod{11} & x^2+4\equiv 5\pmod{11}\\ k=1: & 3^1\equiv 3\pmod{11} & x^2+4\equiv 13\equiv 2\pmod{11}\\ k=2: & 3^2\equiv 9\pmod{11} & x^2+4\equiv 85\equiv 8\pmod{11}\\ k=3: & 3^3\equiv 5\pmod{11} & x^2+4\equiv 29\equiv 7\pmod{11}\\ k=4: & 3^3\equiv 4\pmod{11} & x^2+4\equiv 20\equiv 9\pmod{11}\\ k=5: & 3^5\equiv 1\pmod{11} & \text{and it cycles there...}\\ \end{array}$

So $x^2+4$ is never a multiple of $11$ for any $x=3^k$, and since $3^{k-1}$ is neither divisible by $11$ we have our result for any $k\ge 1$.

• My mistake I miss typed the question. it is 3k-1 not k-1. – AColoredReptile Nov 1 '17 at 23:53
• ok, I propose another method then. – zwim Nov 2 '17 at 0:19