I need help with this divisibility problem. I need help with the following divisibility problem. 
Find all prime numbers m and n such that $mn |12^{n+m}-1$ and $m= n+2$.

Here are some thoughts to start off...
The first twin primes are $(n,m)\in\{(3,5),(5,7),(11,13),(17,19)\}$. Clearly $3\not\mid12^{m+n}-1$ since $12^{m+n}\equiv0\pmod3$. Furthermore, $12^{m+n}\equiv1\pmod{m,n}\implies2,3\not\mid m,n$ and $m+n\equiv0\pmod{m-1,n-1}$, which seems like it could disqualifies many candidates.
However, $11\cdot13=12^2-1\mid12^{24}-1$ so $(11,13)$ is a solution...
If $m=6k+1,~n=6k-1$ is prime, then $m-1=6k\mid m+n=12k$ $\implies$
$12^{12k}\equiv1\pmod m$ for free (from Euler's theorem), while $12^{12k}\equiv1\pmod n$ iff $\operatorname{ord}_n12\mid12k$.
Now


*

*for $k=1$, $\operatorname{ord}_512=4\mid12$;

*for $k=2$, $\operatorname{ord}_{11}12=1\mid24$;

*for $k=3$, $\operatorname{ord}_{17}12=16\not\mid36$;

*for $k=4$, $m$ is not prime;

*for $k=5$, $\operatorname{ord}_{29}12=4\mid12\cdot5$;

*for $k=7$ (the next twin prime pair), $\operatorname{ord}_{41}12=40\not\mid12\cdot7$.


Perhaps there is a good argument why all solutions must be of the form $6k\pm1$.
A little checking in sage shows that @Pedja's solutions, $k=1,2,5$, are the only ones of this form for $k\le10^6$.
for k in range(1,100):
    m = 6*k+1
    n = 6*k-1
    if is_prime(m) and is_prime(n):
        test_order = multiplicative_order(mod(12,6*k-1))
        test_value = 12*k % test_order
        print '%5d%5d%5d%5d%5d' % (k, m, n, test_order, test_value)

1 4
2 1
5 4

In fact, there is a good argument using Fermat's little theorem, and @Michalis presents it in his post.
