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

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...

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$$

• Wish I could learn the mistake here! – lab bhattacharjee May 10 '19 at 11:16
• not introducing your Carmichael function to a lay audience? just a start. – user645636 May 10 '19 at 14:10
• @Roddy, Please find the updated post – lab bhattacharjee May 10 '19 at 14:35
• got the downvote removed ( downvote wasn't me BTW) – user645636 May 10 '19 at 15:06

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.

• can you tell me why you got $22$ in that equation? $m\equiv 22\mod 39$? – trolley May 10 '19 at 11:38
• The Chinese remainder theorem says that there is exactly one $0\leq k<39$ such that $k\equiv 1\mod 3$ and $k\equiv 9\mod 13$ and all solutions are then of the form $k+l\cdot 39$. Now with such low numbers you can just guess $k$ (that's what I did) or you solve the equation $3a+1=13b+9$, i.e. $3a-13b=8$, which can be done with the Euclidean algorithm. – P R May 10 '19 at 11:55

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$$.