Find all $n \in \mathbb{N}$ such that $3^{n}-n$ is divisible by $17$.
Problem
Source:
Tags: algorithm, Divisibility Theory
07.10.2007 12:52
We have that $ 3^8\equiv(3^3)^2*3^2\equiv10^2*3^2\equiv( - 2)*3^2\equiv - 1\bmod{17}$so 3 is primitive root mod17. Clearly 17 does not divide n.Let $ n\equiv{a}\bmod{17}$where $ a\in\left\{1,2,...16\right\}$.Because 3 is primitive root mod17 there is unique $ b\in\left\{1,2,...16\right\}$ such that $ 3^b\equiv{a}\bmod{17}$. So $ 3^n\equiv{n}\equiv{a}\equiv3^b\bmod{17}\Rightarrow n\equiv{b}\bmod{16}$ We conclude that $ n\equiv x\bmod(16*17)$such that$ x\equiv a\bmod{17}$and$ x\equiv{b}\bmod{16}$. This is the algorithm for finding the solutions mod272 We have $ 3\equiv3\mod{17},3^2\equiv9\bmod{17},3^3\equiv10\bmod{17},3^4\equiv13\bmod{17},3^5\equiv5\bmod{17},3^6\equiv15\bmod{17},3^7\equiv11\bmod{17},3^8\equiv16\bmod{17},3^9\equiv14\bmod{17},3^{10}\equiv8\bmod{17},3^{11}\equiv7\bmod{17},3^{12}\equiv4\bmod{17},3^{13}\equiv12\bmod{17},3^{14}\equiv2\bmod{17},3^{15}\equiv6\bmod{17},3^{16}\equiv1\bmod{17}$ If $ a = 1\Rightarrow b = 16\Rightarrow n\equiv256\bmod{272}$ If $ a = 2\Rightarrow b = 14\Rightarrow n\equiv205\bmod{272}$ If $ a = 3\Rightarrow b = 1\Rightarrow n\equiv241\bmod{272}$ If $ a = 4\Rightarrow b = 12\Rightarrow n\equiv140\bmod{272}$ If $ a = 5\Rightarrow b = 5\Rightarrow n\equiv5\bmod{272}$ If $ a = 6\Rightarrow b = 15\Rightarrow n\equiv159\bmod{272}$ If $ a = 7\Rightarrow b = 11\Rightarrow n\equiv75\bmod{272}$ If $ a = 8\Rightarrow b = 10\Rightarrow n\equiv42\bmod{272}$ If $ a = 9\Rightarrow b = 2\Rightarrow n\equiv162\bmod{272}$ If $ a = 10\Rightarrow b = 3\Rightarrow n\equiv163\bmod{272}$ If $ a = 11\Rightarrow b = 7\Rightarrow n\equiv215\bmod{272}$ If $ a = 12\Rightarrow b = 13\Rightarrow n\equiv29\bmod{272}$ If $ a = 13\Rightarrow b = 4\Rightarrow n\equiv132\bmod{272}$ If $ a = 14\Rightarrow b = 9\Rightarrow n\equiv201\bmod{272}$ If $ a = 15\Rightarrow b = 6\Rightarrow n\equiv134\bmod{272}$ If $ a = 16\Rightarrow b = 8\Rightarrow n\equiv152\bmod{272}$ (I correct my wrongs in calculations)
07.10.2007 13:51
So what is your final answer? Not all those n's work, for example $ n = 3$ doesn't work?
07.10.2007 14:02
all such $ n$ are in form $ n=16(17t+r-3^r)+r$ where $ r,t\in\mathbb Z$ which $ 0\leq r\leq 16$ and $ t\geq \frac{3^r-r}{17}$. A boring problem huh?