Sum of k-powers and divisibility

In summary, the conversation revolves around a problem involving a set of positive and distinct integers and the set of prime divisors of numbers formed by taking the sum of powers of the given integers. It is being discussed how to prove that this set of prime divisors is infinite, with a heuristic argument being proposed for even values of $n$. However, the argument does not hold for odd values of $n$ and thus, may not be the correct approach to the problem.
  • #1
Bibubo
14
0
Let $a_{1},\dots,a_{n},\, n>2$ positive and distinct integer. Prove that the set of primes divisors of the numbers $$a_{1}^{k}+\dots+a_{n}^{k}$$with $k\in\mathbb{N}$ is infinite.
 
Mathematics news on Phys.org
  • #2
Any integer has only a finite number of prime divisors. Do you mean to say that the set $S$ consisting of prime factors of numbers _of the form_ $\sum a_i^k$ is infinite? That is pretty easy to prove : there are infinitely many primes of the form $x^2 + y^2$ by Fermat so a subset of $S$ is (countably, of course) infinite, thus all of $S$ is infinite.
 
  • #3
mathbalarka said:
Any integer has only a finite number of prime divisors. Do you mean to say that the set $S$ consisting of prime factors of numbers _of the form_ $\sum a_i^k$ is infinite? That is pretty easy to prove : there are infinitely many primes of the form $x^2 + y^2$ by Fermat so a subset of $S$ is (countably, of course) infinite, thus all of $S$ is infinite.

It looks like he wants to show that for every finite set of integers $\{ a_1, a_2, \cdots, a_n \}$, for $n > 2$, the set of prime factors of the elements of the set:
$$\left \{ \sum_{i = 1}^n a_i^k \mid k \in \mathbb{N} \right \}$$
is infinite.
 
  • #4
Ah, that makes the problem seemingly nontrivial. Interesting.

Bibubo, where did you get this problem?
 
  • #5
mathbalarka said:
Ah, that makes the problem seemingly nontrivial. Interesting.

Bibubo, where did you get this problem?

A friend of mine proposed to me this problem some days ago.
 
  • #6
Well, it looks like a clever choice of values of $k$ to ensure divisibility by a particular sequence of primes might perhaps work, but I have nothing in mind at the moment. In the meantime, here is at least a heuristic argument for even $n$. Take any sequence of primes all larger than all $a_i$, and choose $k_p = (p - 1) / 2$. Then we have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \pmod{p}$$
Where $r_p(a_i)$ is the quadratic character of $a_i$ mod $p$ and is equal to $1$ if $a_i$ is a quadratic residue, $-1$ if $a_i$ a quadratic nonresidue, and $0$ if $p$ divides $a_i$ (not applicable here as $0 < a_i < p$). There is evidence that $r_p(a)$ for $a \in \left ( \mathbb{Z}_p \right )^*$ behaves essentially like a random variable and all we need is that in our set $\{ a_1, a_2, \cdots a_n \}$, half of the $a_i$ be quadratic residues and the other half be quadratic nonresidues. Hence via the binomial distribution this should occur with probability:
$$P = \binom{n}{n/2} \left ( \frac{1}{2} \right )^n$$
For instance $P = 0.375$ for $n = 4$, and $P \approx 0.23$ for $n = 12$. And we will then have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \equiv 0 \pmod{p} ~ ~ \implies ~ ~ p ~ \text{divides} ~ \sum_{i = 1}^n a_i^{k_p}$$
So we can just keep selecting larger and larger primes until that holds, and hence it follows that at least a subset of your $k$-powers should be multiples of arbitrarily large primes, and so there should be infinitely many primes in your set. But I am not happy with this because besides being heuristic, it doesn't work at all for odd $n$, so this is probably not the right way to go about the problem.​
 
  • #7
Bacterius said:
Well, it looks like a clever choice of values of $k$ to ensure divisibility by a particular sequence of primes might perhaps work, but I have nothing in mind at the moment. In the meantime, here is at least a heuristic argument for even $n$. Take any sequence of primes all larger than all $a_i$, and choose $k_p = (p - 1) / 2$. Then we have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \pmod{p}$$
Where $r_p(a_i)$ is the quadratic character of $a_i$ mod $p$ and is equal to $1$ if $a_i$ is a quadratic residue, $-1$ if $a_i$ a quadratic nonresidue, and $0$ if $p$ divides $a_i$ (not applicable here as $0 < a_i < p$). There is evidence that $r_p(a)$ for $a \in \left ( \mathbb{Z}_p \right )^*$ behaves essentially like a random variable and all we need is that in our set $\{ a_1, a_2, \cdots a_n \}$, half of the $a_i$ be quadratic residues and the other half be quadratic nonresidues. Hence via the binomial distribution this should occur with probability:
$$P = \binom{n}{n/2} \left ( \frac{1}{2} \right )^n$$
For instance $P = 0.375$ for $n = 4$, and $P \approx 0.23$ for $n = 12$. And we will then have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \equiv 0 \pmod{p} ~ ~ \implies ~ ~ p ~ \text{divides} ~ \sum_{i = 1}^n a_i^{k_p}$$
So we can just keep selecting larger and larger primes until that holds, and hence it follows that at least a subset of your $k$-powers should be multiples of arbitrarily large primes, and so there should be infinitely many primes in your set. But I am not happy with this because besides being heuristic, it doesn't work at all for odd $n$, so this is probably not the right way to go about the problem.​
I think I get a solution, but I'm not sure. Suppose for absurd that $$\left\{ p\, primes:\, p\mid\underset{i=1}{\overset{n}{\sum}}a_{i}^{k},\, k\in\mathbb{N}\right\} =\left\{ p_{1},\dots,p_{r}\right\}.$$Let $a_{1}+\dots+a_{n}=c$ and let $b_{i}$ the order of $c$ as a element of $\mathbb{Z}/p_{i}\mathbb{Z}.$ Now take $$k=p_{1}\cdots p_{r}b_{1}\cdots b_{r}$$then we have $$\overset{n}{\underset{i=1}{\sum}}a_{i}^{k}\equiv\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{k}=\left(\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{b_{1}}\right)^{p_{1}\cdots p_{r}b_{2}\cdots b_{r}}\equiv1\,\textrm{mod}\, p_{1}$$where the first congruence is for the "freshman's dream" (in this case we have char=$p_{1}$).We can repeat the same argument for every $p_{i}$ and so nobody of the $p_{i}$ divides that sum, which is a contradiction. Is it wrong? Note that I haven't information about $p_{i}$ (they can be greater than $c$ or smaller, they can divide $c$ or not). So I can't show explicit the value of $b_{i}$. Am I wrong? Thank you.
 
  • #8
Bibubo said:
I think I get a solution, but I'm not sure. Suppose for absurd that $$\left\{ p\, primes:\, p\mid\underset{i=1}{\overset{n}{\sum}}a_{i}^{k},\, k\in\mathbb{N}\right\} =\left\{ p_{1},\dots,p_{r}\right\}.$$Let $a_{1}+\dots+a_{n}=c$ and let $b_{i}$ the order of $c$ as a element of $\mathbb{Z}/p_{i}\mathbb{Z}.$ Now take $$k=p_{1}\cdots p_{r}b_{1}\cdots b_{r}$$then we have $$\overset{n}{\underset{i=1}{\sum}}a_{i}^{k}\equiv\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{k}=\left(\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{b_{1}}\right)^{p_{1}\cdots p_{r}b_{2}\cdots b_{r}}\equiv1\,\textrm{mod}\, p_{1}$$where the first congruence is for the "freshman's dream" (in this case we have char=$p_{1}$).We can repeat the same argument for every $p_{i}$ and so nobody of the $p_{i}$ divides that sum, which is a contradiction. Is it wrong? Note that I haven't information about $p_{i}$ (they can be greater than $c$ or smaller, they can divide $c$ or not). So I can't show explicit the value of $b_{i}$. Am I wrong? Thank you.

I believe that doesn't quite work. Note that if we set $k = 1$ then there is at least one $p_i \mid \sum a_i$, such that $p_i$ divides $c$. So $c \equiv 0 \pmod{p_i}$ so $\sum a_i^k \equiv 0 \pmod{p_i}$ for any $k$ multiple of $p_1$ in that case. So the congruence for $p_i$ doesn't really hold for that $k$.

As an example, take $a = (2, 3, 6)$ and consider $k = 1, 2, 3$. We get:
$$2 + 3 + 6 = 11$$
$$2^2 + 3^2 + 6^2 = 49 = 7^2$$
$$2^3 + 3^3 + 6^3 = 216 = 2 \times 11 \times 13$$
So our set of primes here is $\{ 2, 7, 11, 13 \}$. Your proof claims that we can always find a larger $k$ which is not divisible by any of the primes in this set (and hence the set was not in fact complete, showing it must be infinite). Your proof proceeds by taking $c = 2 + 3 + 6 = 11$, and then computing multiplicative orders of $c$ modulo $2, 7, 11, 13$. But $c$ has no order modulo 11! Even if we redefine $b_i$ as something sensible like $p_i - 1$ (since $b_i$ must divide $p_1 - 1$ by Lagrange's theorem) your congruence fails for 11, and in fact $11$ will divide $\sum a_i^k$ for any $k$ divisible by 11.

So the congruence does not hold for all primes in the set, and so it does not follow that $\sum a_i^k$ for such $k$ must be divisible by a prime not in the set.

I like your approach though. It might be possible to modify it so that it does work!
 
  • #9
Bacterius said:
I believe that doesn't quite work. Note that if we set $k = 1$ then there is at least one $p_i \mid \sum a_i$, such that $p_i$ divides $c$. So $c \equiv 0 \pmod{p_i}$ so $\sum a_i^k \equiv 0 \pmod{p_i}$ for any $k$ multiple of $p_1$ in that case. So the congruence for $p_i$ doesn't really hold for that $k$.

As an example, take $a = (2, 3, 6)$ and consider $k = 1, 2, 3$. We get:
$$2 + 3 + 6 = 11$$
$$2^2 + 3^2 + 6^2 = 49 = 7^2$$
$$2^3 + 3^3 + 6^3 = 216 = 2 \times 11 \times 13$$
So our set of primes here is $\{ 2, 7, 11, 13 \}$. Your proof claims that we can always find a larger $k$ which is not divisible by any of the primes in this set (and hence the set was not in fact complete, showing it must be infinite). Your proof proceeds by taking $c = 2 + 3 + 6 = 11$, and then computing multiplicative orders of $c$ modulo $2, 7, 11, 13$. But $c$ has no order modulo 11! Even if we redefine $b_i$ as something sensible like $p_i - 1$ (since $b_i$ must divide $p_1 - 1$ by Lagrange's theorem) your congruence fails for 11, and in fact $11$ will divide $\sum a_i^k$ for any $k$ divisible by 11.

So the congruence does not hold for all primes in the set, and so it does not follow that $\sum a_i^k$ for such $k$ must be divisible by a prime not in the set.

I like your approach though. It might be possible to modify it so that it does work!
Thank you so much for your observations! I will try to fix these errors.
 

FAQ: Sum of k-powers and divisibility

What is the sum of k-powers?

The sum of k-powers refers to the sum of numbers raised to a power of k, where k is a positive integer. For example, the sum of 2-powers would be written as 21 + 22 + 23 + ... up to the desired number of terms.

How is the sum of k-powers useful in mathematics?

The sum of k-powers is useful in various mathematical concepts, such as number theory and algebra. It can also be used in the study of sequences and series, as well as in solving problems involving polynomials.

What is the relationship between the sum of k-powers and divisibility?

The sum of k-powers can be used to determine the divisibility of a number by certain factors. For example, the sum of 3-powers can be used to determine if a number is divisible by 7, as there is a specific pattern in the sum of 3-powers for numbers that are divisible by 7.

How can the sum of k-powers be used to find the remainder of a division?

In some cases, the sum of k-powers can be used to find the remainder of a division. This is particularly useful in number theory, where it can be used to solve problems involving modular arithmetic.

Are there any special cases or exceptions when using the sum of k-powers for divisibility?

Yes, there are certain cases where the sum of k-powers method may not work for determining divisibility. For example, using the sum of 3-powers to determine divisibility by 7 does not work for numbers that are multiples of 3. It is important to be aware of these exceptions when using this method.

Similar threads

Replies
1
Views
1K
Replies
1
Views
987
Replies
2
Views
1K
Replies
1
Views
1K
Replies
3
Views
1K
Replies
5
Views
1K
Replies
4
Views
2K
Replies
2
Views
1K
Back
Top