I have a large integer, 422215686281216. I am looking for two fifth powers which when added together, or subtracted from one another, equal this number. How can I tell whether an integer is the sum , or difference, of two fifth powers ?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
10
You can show that sums and differences of two fifth powers cannot be congruent to $3$ modulo $11$.
Then note that your number is congruent to $3$ modulo $11$.
Conclude that you cannot write your number as a sum or difference of two fifth powers.
Added: Oh, so many opinions and helpful comments. To clarify, I merely calculated sums and differences of fifth powers modulo $2, 3, 4,$ etc. until I found a modulus for which not all congruence classes were possible. This happened to be $11$, and it just happened that one class left out, $3$, was the class of the given number. This is a standard method for treating these sums-of-powers questions. For further reading, take a look at most any introductory number theory text (let me know if you would like a more specific reference).
answered Apr 5 '17 at 22:32
-
1$\begingroup$ Why $3$ and $11$? Does this fit in a more general statement? $\endgroup$ – Couchy Apr 5 '17 at 22:43
-
2$\begingroup$ Possible values of a difference of $5$'th powers mod $11$ are $0, 1, 2, 9, 10$. $11$ is the smallest modulus for which not everything is a possible value. $\endgroup$ – Robert Israel Apr 5 '17 at 22:49
-
2$\begingroup$ It's a good idea to try $11$ because $\phi(11)=10$ so $a^{10} \equiv 1 \pmod{11}$ for all $a$, and (since $11$ is prime) $a^{5} \equiv \pm 1$ for all $a$. If $11$ didn't work (for example, if the number were divisible by $11$) then we could try other numbers $n$ such that $\phi(n)$ is a small multiple of $5$, such as $25$ or $31$. $\endgroup$ – Misha Lavrov Apr 5 '17 at 22:54
-
1$\begingroup$ @RobArthan Why? That's a pretty common approach to these types of problems. $\endgroup$ – Oiler Apr 5 '17 at 23:10
-
1
$\begingroup$
$\endgroup$
1
Here's something you could try if Matthew Conroy's trick didn't work.
More generally, suppose you have a positive integer $N$ and you want to write $N = x^5 - y^5$ where $x$ and $y$ are integers (this includes a sum of $5$'th powers if you take $y$ to be negative). Note that $$ N = (x - y)(x^4 + x^3 y + x^2 y^2 + x y^3 + y^4)$$ so $x - y$ must be one of the (positive or negative) divisors of $N$. Enumerate all divisors of $N$ (which you can do from the prime factorization); for each such divisor $d$, check whether the polynomial $(Y+d)^5 - Y^5 - N$ has an integer root. If it does (say $r$), then $y = r$, $x = r+d$ is a solution. If none of these has an integer root, it is not possible to write $N$ as a sum or difference of $5$'th powers.
answered Apr 5 '17 at 22:57
-
$\begingroup$ Excellent Answer. Thanks very much Robert Israel. $\endgroup$ – Derek Apr 5 '17 at 23:16
