So, I've encountered this problem and solved it using the hombo bombo technique. If you're not familiar with the topic, it's a technique I use to solve pretty much any math problem:
Brute force the answer.
Try to find any patterns.
However, I felt this problem is different. Here's what I did:
Usually, it ends here and I never look at the problem again. But for this particular problem, it was a little too much to say "yeah the pattern is obvious.". How counting modules for 2 seemingly different expressions have anything to do with powers of 2. So, I tried playing a little bit with binomial coefficients and no luck. So, I collected my questions:
In the bruteforce solution, I was checking different values of $$$m$$$, but I didn't know the upper bound of $$$m$$$. For example: when $$$n = 35$$$, biggest $$$m$$$ that satisfied the equation was $$$4$$$. For $$$n = 37$$$, however, biggest $$$m$$$ was $$$1919190$$$. What does this value depend on?
Also, it was sufficient to check values for $$$a$$$, $$$b$$$ up to $$$3$$$ only, this yielded the same solutions. Don't know is it because small value of $$$m$$$ or what.
Most importantly, how to start solving it and similar problems, instead of just making some bruteforce and hoping the pattern magically appears.
How is the answer related to Bernoulli numbers, let alone this sequence A086668?
I did search for the exact expression but no luck. I'm interested in the solution and some kind of a proof. Thanks in advance and appreciate any help.
It's actually quite interesting if there is a very a neat proof maybe Hosen_ba could help!
If $$$n$$$ is even, $$$a=-1$$$, $$$b=1$$$ implies $$$m=1,2$$$. If $$$n$$$ is odd, then consider each prime power $$$p^k$$$ dividing $$$m$$$. The condition is equivalent to $$$a^n\equiv a\pmod{p^k}$$$. If $$$k$$$ is at least $$$2$$$, then $$$a=p^{k-1}$$$ gives a contradiction. Therefore, $$$k=1$$$, so $$$p-1\mid n-1$$$. Therefore, the number of solutions is $$$2$$$ to the power of the number of primes $$$p$$$ satisfying $$$p-1\mid n-1$$$, which happens to give exactly the sequence you mentioned after accounting for $$$p=2$$$.
How can $$$a=-1$$$ when both $$$a$$$ and $$$b$$$ must be natural numbers?
Can you explain with a bit more steps/clarification how the condition is equivalent to $$$a^n≡a\pmod{p^k}$$$? I'm not very good at number theory
Suppose that the condition is true. It's already obvious that $$$0^n \equiv 0 \pmod m$$$ and $$$1^n \equiv 1 \pmod m$$$. From the condition, it follows that $$$2^n \equiv (1 + 1)^n \equiv 1^n + 1^n \equiv 2 \pmod m$$$, and therefore $$$3^n \equiv (1 + 2)^n \equiv 1^n + 2^n \equiv 3 \pmod m$$$, and so on.
To change the modulus from $$$m$$$ to all of the $$$p^k$$$ which divide it, the $$$\implies$$$ direction is obvious, and the $$$\impliedby$$$ direction follows from the Chinese Remainder Theorem.
And in case you didn't figure out the first question, for fixed $$$m$$$, we don't really care about the natural numbers themselves, but instead we care about their residues modulo $$$m$$$. So $$$-1$$$ really means $$$\{m - 1, 2m - 1, 3m - 1, ...\}$$$ (for $$$m \gt 1$$$).