4
$\begingroup$

The problem is to find a prime factor of $N = 8^9 - 9^8.$

We have $N = 91171007 = 257 \cdot 354751$ by brute force. The observation that $257 = 2^8 + 1$ leads us to a crossroad:

  1. There is an elegant solution relying on this observation.

  2. The person who proposed this problem was trolling.

Hopefully, the latter scenario is false, and one of us can dig up the solution.

Some ideas to consider:

Sophie Germain's identity

Generalizing to the problem of factoring $8x^8 - y^8.$

Choosing $n$ for which factoring $2^{3n} x^{9-n} - y^8$ is tractable.

Looking at a similar generalization obtained by dragging one or more primes out of $8^9$ or $9^8$

We have $2^8 + 1 = 4 \cdot 8^2 + 1^2;$ try reverse engineering?

Edit: The solution should appear natural to one who does not know a priori that $257$ is a factor. Sirous's approach fails this test.

$\endgroup$

1 Answer 1

1
$\begingroup$

$$N=8^9-9^8$$

$$N+9^8=8^9$$

$$N+9^8+8=8^9+8=8(8^8+1)$$

$$8^8+1=(2^3)^8+1=(2^8)^3+1=(2^8+1)(2^{16}-2^8+1)$$

Therefore:

$N+9^8+8= 257 m$

We can see that $9^8+8=43046729=257\times 167497$

That is N must also be divisible by 257. But if we want to continue calculating,

$9^8+8=(8+1)^8+8=2(8^8+1)+28\times 8^6+56\times8^5+70\times8^4+56\times8^3+28\times8^2+8^2-1+8$

$8^8+1 ≡0 \mod 257$

$8^6 ≡-4\mod 257$$28\times 8^6 ≡-112\mod 257$

Similarly we can find the remainder of terms when divided by 257, the sum of remainders must be zero.

Generally for number such as $N=\alpha^{\alpha ±1}-(\alpha ±1)^{\alpha}$ or particular case $N=(2k+1)^{2k+2}-(2k+2)^{2k+1}$ we may consider following points:

a) $\alpha=2k+2=p-1$ where p is a prime then we have:

$(2k)^{p-1} ≡1 \mod (p)$

$2k+2≡-1\mod (p)$

$N=(2k+1)^{2k+2}-(2k+2)^{2k+1}≡2 \mod(p)$

Example:

$N=221^{222}-222^{221}$

$221^{222}=221^{223-1}≡1 \mod (223)$

$222^{221}≡-1 \mod(223)$

$N=221^{222}-222^{221}≡2\mod(223)$

So odd numbers such as 225, 671, . . . could potentially be a factor of N.

b) $2k+2+1$ is not prime, then we can take a prime closest to $2k+2$. For example for $N=8^9-9^8$ we may write:

$8^9=\frac{8^{10}}{8}=\frac{1\mod (11)}{8}$

$9^8=\frac{9^{10}}{9^2}=\frac{1 \mod (11)}{81}$

$8^9-9^8≡(\frac{1}{8}-\frac{1}{81}) \mod 11≡\frac{73}{736}\ mod (11)$

$736 N≡73 \mod (11)$

$73 ≡ -4 \mod(11)$

$736≡-1 \mod 11$

$(-1 mod (11))(8^9-9^8)≡ -4 \mod (11)$

$8^9-9^8≡4 \mod (11)$

So odd numbers such as 15, 43, ... , 257 etc can potentially be factors of N.

Another example:

$N=7^8-8^7$

$7^8=\frac{7^{10}}{49}≡\frac{1}{49}\mod(11)≡ \frac{1}{5}\mod (11)$

$8^7=\frac{8^{10}}{8^3}≡\frac{1\mod (11)}{6 \mod (11)}$

Which after some calculation gives $N=7^8-8^7 ≡ 1 \mod (11)$

Therefore odd numbers such as 23, 45 , etc could be a factor of N.

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