Solving a congruence $a^k\equiv 1 \pmod k$ $a^k\equiv 1 \pmod k. $ $a$ is a given positive integer. Solve for $k$ over the integers. And for what a are there solutions for k?
Also if we have a prime $p$, for what positive integer $m$ does $m|p^m -1$?
Well I tried doing some stuff with the order of $a$ modulo $k$, but actually, I'm not even sure how to approach this so it's been quite fruitless. Can someone help?
 A: Just a partial example, giving many answers, but no idea if it is all.
If $k\mid a-1,$ you get a trivial solution.
If $k=p$ is prime, it is true if and only if $p\mid a- 1.$ So you only get trivial answers when $k$ is prime.
More generally, if $k=p^i$ with $p$ a prime, then $$a^{p^{i-1}}=a^{p^i-\phi(p^i)}\equiv 1\pmod{p^i}.$$ This means, again, that $a\equiv 1\pmod p.$ But this gives solutions where $k\not\mid a-1.$
If $k=pq$ with $p<q$ prime, then $$a^{\gcd(\phi(pq),pq)}\equiv 1\pmod {pq}.$$ For non-trivial solutions, this means we need $\gcd(pq,\phi(pq))\neq 1.$ This is equivalent to $p\mid q-1.$
Then $\gcd(pq,\phi(pq))=p.$ So $pq\mid a^p
-1.$ But we showed that this means $p\mid a-1.$
So you need $q\mid a^p-1.$ If you have $q\mid a-1,$ then $k\mid a-1,$ and you have a trivial solution again. You can pick any prime factor $q$ of $a^p-1$ which is not a factor of $p(a-1)$ to get a nontrivial solution. For all such $q,$ $q\equiv 1\pmod p.$
So, for example, with $p=3,$ $a\equiv 1\pmod 3,$ $q=7$ has $a^3\equiv 1\pmod 7,$ so $a^{21}\equiv 1\pmod{21}.$
It seems like you might be able to generalize this. If $p$ is a prime divisor of $a-1,$ let $k’$ be any factor of $a^p-1$ relatively prime to $p.$ Then $k=pk’$ is a solution, because $p\mid a-1\mid a^k-1$ and $k’\mid a^p-1\mid a^k-1.$
For example, $a=8,p=7$ gives $$8^7-1=7^2\cdot 127\cdot 337.$$ So you can take $k=7\cdot 127\cdot 337=299593.$
That gives a very large class of answers, but probably not all.
If $a,k$ is a solution, and $p\mid k$ is prime, then $a,kp$ is a solution. This shows that any $k’$ with $k\mid k’\mid k^n,$ will be a solution.
