How many integers $m$ such that $9^m - m$ is divisible by $65$

Question

How many integers $m$ such that $9^m - m$ is divisible by $65$ where $1\le m \le 1000$ $\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}$

My approach

Generally we want to solve: $$ 9^m \equiv m \Mod{65} $$ From Chinese remainder theorem we know that this is equivalent to: $$ 9^m \equiv m \Mod{13} \wedge 9^m \equiv m \Mod{5} $$

1. After write some first elements from $9^m$ we see that $$ 9^m \text{ mod } 5 = \begin{cases} 4 \text{ when m is odd} \\ 1 \text{ when m is even} \end{cases}$$ so we are thinking about all numbers which have $6,9$ at first digit.
2. After write some first elements from $9^m$ we see that $$ 9^m \text{ mod } 13 = \begin{cases} 9 \text{ when m = 3k+ 1} \\ 3\text{ when m = 3k+ 2} \\ 1\text{ when m = 3k} \end{cases} $$ we see that for $m=3k+1$ and for $m=3k+2$ there is no chance to have the same remainder. So we want every $m$ in form of $m=3k$ which is dividable by $13$. So we want each $m$ dividable by $39$. It will be: $$ 39, 78, 117, 156, 195, 234, 273, 312, 351, 390, 429, 468, 507, 546, 585, 624, 663, 702, 741, 780, 819, 858, 897, 936, 975 $$ We choose these number which pass condition in $(1)$ and we get $$39, 156, 429, 546, 819, 936, $$

but this is wrong answer... It should be $16$ numbers...

Answer 1

Hint:

As $65=13\cdot5$

$3^3\equiv1\pmod{13}\implies9^3\equiv1\implies$ord$_{13}9=3$

and similarly ord$_59=2$

$\implies$ord$_{65}=[3,2]=6$

This is instantly available from http://mathworld.wolfram.com/CarmichaelFunction.html

So, there can be $12/2$ unique values of $9^m=3^{2m}$

namely $0\le m<6$

$m\equiv0\pmod6,9^m\equiv1\pmod{65}$

So, for $m=6n,$

$9^m-m\equiv1-6n\pmod{65},n=11+65r,m=6(11+65r)$

For $m=6n+1$

$9^m-m\equiv9-(6n+1)\pmod{65}\iff3n\equiv4+65\iff n\equiv23,m=1+6(23+65r)$

Similarly check for $m=6n+2,6n+3,6n+4,6n+5$

Answer 2

The mistake appears in (2), there are values for $m$ such that $m\equiv 1\mod 3$ and $m\equiv 9\mod 13$. By Chinese remainder theorem these are exactly all $m\equiv 22\mod 39$. You can handle the second and third case anaologously. Note that you don't want $m$ to be divisible by $13$ in the third case (as you stated), but $m\equiv 1\mod 13$.

Note also that you can combine these conditions with case (1), instead of writing all $m$ down and picking those which satisfy (1). For example, $m\equiv 22\mod 39$ and $m\equiv 6\mod 10$ is equivalent to $m\equiv 256\mod 390$, so you are left with only two values for $m\leq 1000$ here.

Answer 3

You mistook the possible residues $\bmod 13$. Multiples of $39$ do not work (e.g. $9^{39}\not=39\bmod 13$), and there are non-multiples of $39$ that do.

Properly, powers of $9\bmod 13$ are given by $9^1\equiv 9, 9^2\equiv 3, 9^3\equiv 1$ and cyclic repetitions. So $m\in\{1,3,9\}\bmod 13$ and for each of these residues, $m\bmod 3$ must have the right residue to match the cyclic pattern of powers:

$m\equiv 1\bmod 13$ AND $m\equiv 0\bmod 3$

$m\equiv 3\bmod 13$ AND $m\equiv 1\bmod 3$

$m\equiv 9\bmod 13$ AND $m\equiv 2\bmod 3$

Working through each possibility with CRT then renders $m\in\{16,27,35\}\bmod 39$, which you must "marry" with the correctly derived requirement that $n$ end in $6$ or $9$ base $10$. For instance, $m\equiv 16\bmod 39$ gives $16, 406, 796$ ending in $6$ and $289, 679$ ending in $9$. You get $16$ solutions in all among the three accepted residues $\bmod 39$.