2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you tell me why you got $22$ in that equation? $m\equiv 22\mod 39$? $\endgroup$ – trolley May 10 '19 at 11:38
  • $\begingroup$ 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. $\endgroup$ – P R May 10 '19 at 11:55
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.