1
$\begingroup$

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

  • 0
    What theorems do you know that could be helpful for this problem?2012-04-09
  • 0
    $(5,7),(11,13),(29,31)$2012-04-09
  • 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)$.2012-04-09

2 Answers 2

2

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

  • 0
    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?2012-04-09
  • 1
    I think I fixed the TeX, but I'm not sure which moduli your congruences are using. You can use `\pmod{...}` for that.2012-04-09
  • 0
    I don't see how you got $143$, could you elaborate?2012-04-09
  • 0
    @Gigili: $12^2-1|12^{2k}-1$ for all $k\in\mathbb{N}$2012-04-09
  • 0
    Ah yes, thank you @bgins.2012-04-09
  • 0
    This isn't enough to make that deduction. Surely $12^{p+1}\pm1$ have other prime factors. It is a nice *sufficient* condition, but not a *necessary* one.2012-04-09
  • 0
    @bgins: I am saying that in order to solve the problem $p$ necessarily divides $12^{p+1}+1$ or $12^{p+1}-1$. $12^{p+1}-1$ (resp. $+1$) is divisible by $p$ iff $p=11,13$ (resp $5,29$).2012-04-09
  • 0
    For example, $p,p+2$ could divide $\Phi_d(12)$ for any $d|2(p+1)$ since $x^t\pm1=\prod_{d|\frac{3\pm1}{2}t}\Phi_d(x)$.2012-04-09
  • 0
    I think the argument is okay, but could use a little more explanation. Since $12^{p-1}-1$ is divisible by $p,$ we do have $12^{p+1} -1 \equiv 143$ (mod $p$) and $12^{p+1}+1 \equiv 145$ (mod $p$). But given that $p$ divides the product of these two numbers, either $143$ or $145$ must be divisible by $p.$ Since we are told that $p+2$ must be prime, we can't havd $p =13.$ Also, since $p+2$ is prime, $12^{p+1}-1$ is divisible by $p+2.$2012-04-09
  • 0
    @bgins: I'm sorry I still don't get your remark. I added some details to my answer, do you still think it's wrong? I see one mistake you made though. The 143,145 both come from Fermat's little theorem and not from $12^2|12^{2k}-1$.2012-04-09
  • 0
    Okay, I'm convinced now. Looks great! You should also mention as @GeoffRobinson (and I did in my post) that we get $p+2|12^{p+1}-1$ "for free" from Euler's theorem since $\operatorname{ord}_{p+2}(12)|\phi(p+2)=p+1$.2012-04-09
  • 0
    @bgins: Thanks, added!2012-04-09
  • 0
    I was confused because I didn't see that you were using Fermat's little theorem and looking at these `\pmod p`; in my confusion, I glossed over that and assumed you were using the property of primes that $p|ab \implies p|a$ or $p|b$. I changed the TeX to reflect that (the `\mod p` wasn't rendering at all on my system -- even hiding the $p$), lest anyone else make my mistake.2012-04-09
  • 0
    I would start your post off like this: You want to solve $p(p+2)|(12^{p+1}-1)(12^{p+1}+1)$. Clearly $p\ne2,3$ since $12^{2p+2}\equiv1\pmod p$. For the larger prime, $(p+2)|(12^{p+1}-1)$ follows from Euler's theorem: $\operatorname{ord}_{p+2}(12)\,|\,\phi(p+2)=p+1$. From the smaller prime, we can then solve the problem.2012-04-09
0

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.