Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What theorems do you know that could be helpful for this problem? –  Phira Apr 9 '12 at 8:47
    
$(5,7),(11,13),(29,31)$ –  pedja Apr 9 '12 at 8:48
1  
You have primes $p$ and $p+2$, and you want to choose $p$ so that $p(p+2)\mid 12^{2p+2}-1=\left(12^{p+1}-1\right)\left(12^{p+1}+1\right)$. –  Brian M. Scott Apr 9 '12 at 8:55
add comment

2 Answers

up vote 2 down vote accepted

You want to solve $p(p+2)|(12^{p+1}-1)(12^{p+1}+1)$.

Hint: First exclude $p=2,3$, so we have $$\eqalign{ 12^{p+1}-1 \equiv 143 &= 11 \cdot 13 &\pmod p,\\ 12^{p+1}+1 \equiv 145 &= 5 \cdot 29 &\pmod p, }$$ and deduce that $p$ must be one of $5,11,29$.

Edit: I'll just add more details: We want that $p$ divides $(12^{p+1}-1)(12^{p+1}+1)$, so $p$ must divide one of the factors of this product. Suppose $p|12^{p+1}-1=k\cdot p+143$ (the congruence follows from Fermat's little theorem). This means $p|143$ and hence $p=11$ or $p=13$. If $p+2$ is prime then we automatically have $p+2|12^{p+1}-1$ again by Fermat's theorem, so $p=11$ is a solution. $p=13$ isn't, as $p+2$ is not prime.

In the other case, $p|12^{p+1}+1$ we get 2 solutions, $p=5$ and $p=29$.

share|improve this answer
    
Something's wrong with the tex-compiler. I wanted to insert a linebreak into the equations, which is properly displayed in the preview, but not here. Does anybody find my mistake? –  Michalis Apr 9 '12 at 9:41
1  
I think I fixed the TeX, but I'm not sure which moduli your congruences are using. You can use \pmod{...} for that. –  bgins Apr 9 '12 at 9:42
    
I don't see how you got $143$, could you elaborate? –  Gigili Apr 9 '12 at 9:43
    
@Gigili: $12^2-1|12^{2k}-1$ for all $k\in\mathbb{N}$ –  bgins Apr 9 '12 at 9:44
    
Ah yes, thank you @bgins. –  Gigili Apr 9 '12 at 9:46
show 9 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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