I would like to solve this problem using the idea of congruence module m, but I have no idea how to start. Could someone help me?
If $n> 0$ and $n$ is not a multiple of $3$, prove that $a = 3^{2n} + 3^n + 1$ is divisible by $13$.
Asked
Active
Viewed 44 times
0
-
1What have you tried? – Calvin Lin Nov 20 '20 at 18:07
-
$3^3\equiv1\bmod13$ – J. W. Tanner Nov 20 '20 at 18:16
-
$(a-1)(a^2+a+1) = ?$ – rtybase Nov 20 '20 at 18:19
2 Answers
0
$3^3=27=2\times13+1\equiv1\bmod13$, so $3^{3n}\equiv 1 \bmod 13$,
so $3^{3n}-1=(3^n-1)(3^{2n}+3^n+1)\equiv 0\bmod13$,
which means $3^n-1\equiv0\bmod13$ or $3^{2n}+3^n+1\equiv0\bmod13$.
Can you take it from here?
J. W. Tanner
- 60,406
-
It has now become much clearer how to resolve this question.
Thank you for your help.
– Thais Nov 20 '20 at 18:22
0
The simplest way to think in such a situation is to make a table of the data, working modulo $13$, i.e. in the ring $R=\Bbb Z/13$. The table is: $$ \begin{array}{|r|c|l|} \hline n & 3^n\in R & 3^{2n}+3^n+1\in R\\\hline 0 & 1 & 1+1+1 = 3\\ 1 & 3 & 9+3+1 = 13=0\\ 2 & 9 & 3+9+1 = 13=0\\\hline 3 & 1 & 1+1+1 = 3\\ 4 & 3 & 9+3+1 = 13=0\\ 5 & 9 & 3+9+1 = 13=0\\\hline \vdots & \vdots & \vdots \end{array} $$ and it repeats itself. The main point is to see that the powers of $3\in R$ repeat with period three, and then check these three cases.
dan_fulea
- 32,856
-
could prove by induction: base cases $3^2+3+1$ and $3^4+3^2+1$ are divisible by $13$, and $3^{2(n+3)}+3^{n+3}+1=729\cdot3^{2n}+27\cdot3^n+1\equiv3^{2n}+3^n+1\bmod13$ – J. W. Tanner Nov 20 '20 at 19:00
-
This is already too complicated, "induction for us" is not "induction for an exam". Here it is enough to compute the powers $3^0$, $3^1$, $3^2$, $3^3$, so we have here periodicitiy for the only piece that counts, $3^n$, so the first three cases are enough, and now we have simple computations, no logic, no other issues that are easy but annoying to type to care of... @J-W-Tanner (and it takes a lot of time to find this (at)) – dan_fulea Nov 20 '20 at 20:23
-
-