0
$\begingroup$

Find a prime divisor of

a) $2^{49} + 1$

b) $50^{125}-1$

c) $2^{49} -1$

d) $2^{52} +1$

Note that $2^m+1$ is not prime unless $m=2^k$, $2^m-1$ is not a prime unless m is prime.

I checked all the number are composite considering the note given.

I solved (c) by factoring it as $$(2^7+1)(2^7-1)= (3)(43)(187)$$

Tried to do the same with (a) by writing it as $$(2^7+1)(2^7-1)+2$$ but not sure what to do after.

For (b), I tried to write it as $(50^{25})^5-1$. Since it's a Mersenne number and 5 is prime, the divisor must be in the form $$d= 1+(2)(k)(5) = 10k+1$$ but again not sure what to do after. Can't use guess and check because the number is too large.

Would really appreciate if someone could point me in the right direction.

$\endgroup$
  • 1
    $\begingroup$ $3$ divides $2^{49} + 1$ $\endgroup$ – ab123 Nov 10 '18 at 15:45
  • 2
    $\begingroup$ $(a+1)^n-1$ is divisible by $a$ from the binomial theorem. Therefore $50^{125}-1=(49+1)^{125}-1$ has a factor $49.$ $\endgroup$ – gammatester Nov 10 '18 at 15:50
  • $\begingroup$ Is this five problems where you just find one prime divisor of each and not worry about any other? Or are you supposed to find a prime divisor common to all? $\endgroup$ – fleablood Nov 10 '18 at 16:11
  • $\begingroup$ Similarly $(a-1)^n+1$ is divisible by $a$ for positive odd $n$. For d), $2^{52}+1=16^{13}+1$, so d) has a factor $17$. $\endgroup$ – Tianlalu Nov 10 '18 at 16:11
  • $\begingroup$ About c) $(2^{49} -1) \ne (2^7 + 1)(2^7 - 1) = 2^{14} -1$ $\endgroup$ – fleablood Nov 10 '18 at 16:13
1
$\begingroup$

If you are only supposed to find one prime for each.

The main idea seems to be that $(a^k - 1)|(a^{km} -1)$ (as $(a^k-1)(a^{(m-1)k} + ..... + 1) = (a^{km} - 1)$.

However if $m$ is odd you can also have $(a^k + 1)|(a^{km} + 1)$ as $(a^k+1)(a^{(m-1)k} - .....+a^{2k} - a^k + 1) = (a^{km}+1)$

And if $m$ is even you can have $(a^k+1)|(a^{km} -1)$ as $(a^k+1)(a^{(m-1)k} - .....-a^{2k} + a^k -1) = (a^{km}+1)$.

a) $2^{49} + 1$. As $2\equiv -1$ then $2^{odd} + 1\equiv -1 + 1 \pmod 3$ so $3|2^{odd} + 1$. So $3|2^{49} + 1$. That's my answer and I'm sticking with it.

From their hint maybe you were supposed to realize that $(2^7 + 1)(2^{42} - 2^{35} + ..... +2^{14} - 2^7 + 1) = 2^{49} + 1$.

And $2^7 + 1 = 129 = 3*43$.

b) $50^{125} - 1 = (50-1)(50^{124} + ..... + 1)$ so $50-1 = 49$ is a divisor and $7$ is a prime divisor.

c) Note: $(2^7 + 1)(2^7 - 1) \ne 2^{49} - 1$ as you claimed.

But $2^{49} - 1 = (2^7 -1)(2^{35} + .... + 1$ and $2^7 - 1 = 127$ is prime.

d) The hint says $2^m + 1$ is not prime unless $m = 2^k$. There reason for that is is $m \ne 2^k$ then $m = 2^k*j$ for an odd $j$.

And $(2^{2^k} + 1)(2^{(j-1)2^k} - 2^{(j-2)2^k} + ..... +2^{2*2^k} - 2^{2k} + 1) = 2^{2^kj} + 1$.

So $(2^4 + 1)|2^{4*13} + 1$.

So $17$ is a prime factor of $2^{52} + 1$.

$\endgroup$
  • $\begingroup$ That makes sense thank you! $\endgroup$ – Lin Nov 10 '18 at 17:57
0
$\begingroup$

HINT:

For a) and b), we can use the formula (by putting $b=1$ or $-1$) \begin{align*} a^n+b^n=(a+b)\sum_{k=0}^{n-1}(-1)^ka^{n-k-1}b^k\quad \forall \text{positive odd }n.\tag{*} \end{align*} For c), write $$2^{49}-1=(2^7)^7-1=128^7-1,$$ so you can use $(*)$.

For d), \begin{align*} 2^{52}+1&=(2^4)^{13}+1=16^{13}+1, \end{align*} so you can use $(*)$ again.

$\endgroup$
  • $\begingroup$ math.stackexchange.com/questions/695266/…. Replacing y by -y you get factorization of a^n+b^n.Helps? $\endgroup$ – Peter Szilas Nov 10 '18 at 16:48
  • $\begingroup$ @PeterSzilas : That's great! I will insert this link in my answer (^▽^) $\endgroup$ – Tianlalu Nov 10 '18 at 16:53
  • $\begingroup$ Tianlalu. Fairly easily you get your answers ;) $\endgroup$ – Peter Szilas Nov 10 '18 at 16:58
0
$\begingroup$

For first and fourth you can use

$$2^2\equiv 1\pmod3$$

And for the second

$50\equiv 1\pmod7$

Further, $2^{49}$ is not same as $(2^7)^2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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