Why is $p_i + \frac{k}{p_i}$ divisible by $3$ and $8$?

  • MHB
  • Thread starter lfdahl
  • Start date
  • Tags
    Sum
In summary, the problem states that for a natural number $k$ where $k+1 \equiv 0 \:\: (mod\:\:24)$, the sum of $k$´s divisors is also divisible by $24$. The solution shows that this is true by considering the divisors of $k$ and using the fact that $k$ can be written as $4n_1+3$, $3n_2+2$, and $8n_3+7$. By showing that $(1+p)(1+\frac{k}{p})$ is divisible by $3$ and $8$, it follows that the sum of all $k$´s divisors is also divisible by $24
  • #1
lfdahl
Gold Member
MHB
749
0
Problem:
Let $k$ be a natural number, and $k+1 \equiv 0 \:\: (mod\:\:24)$

Show, that the sum of $k$´s divisors is also divisible by $24$.

Solution:
First, note that since $k = 4n_1+3$ for some $n_1\in \mathbb{N}$, $\sqrt{k}$ is not a natural number.

Let $p_1,p_2,…,p_m < \sqrt{k}$ be all $k$´s divisors smaller than $\sqrt{k}$.

Then, the sum of all $k$´s divisors is: $\sum_{i=1}^{m}\left ( p_i+\frac{k}{p_i} \right )$.

Now, since $k = 3n_2+2$ and $k = 8n_3+7$, and $k = p_i\frac{k}{p_i}$, the term $p_i+\frac{k}{p_i}$ is divisible by $3$ and $8$.

Thus, the sum : $\sum_{i=1}^{m}\left ( p_i+\frac{k}{p_i} \right )$ is also divisible by 24.

Can someone explain to me, why $p_i+\frac{k}{p_i}$ is divisible by $3$ and $8$??

Thankyou in advance!
 
Mathematics news on Phys.org
  • #2
lfdahl said:
Problem:
Let $k$ be a natural number, and $k+1 \equiv 0 \:\: (mod\:\:24)$

Show, that the sum of $k$´s divisors is also divisible by $24$.

Solution:
First, note that since $k = 4n_1+3$ for some $n_1\in \mathbb{N}$, $\sqrt{k}$ is not a natural number.

Let $p_1,p_2,…,p_m < \sqrt{k}$ be all $k$´s divisors smaller than $\sqrt{k}$.

Then, the sum of all $k$´s divisors is: $\sum_{i=1}^{m}\left ( p_i+\frac{k}{p_i} \right )$.

Now, since $k = 3n_2+2$ and $k = 8n_3+7$, and $k = p_i\frac{k}{p_i}$, the term $p_i+\frac{k}{p_i}$ is divisible by $3$ and $8$.

Thus, the sum : $\sum_{i=1}^{m}\left ( p_i+\frac{k}{p_i} \right )$ is also divisible by 24.

Can someone explain to me, why $p_i+\frac{k}{p_i}$ is divisible by $3$ and $8$??

Thankyou in advance!
Hint: Let $p$ be a divisor of $k$. Can you show that $(1+p)\Bigl(1+\dfrac kp\Bigr)$ is divisible by $3$ and by $8$?
 
  • #3
Opalg said:
Hint: Let $p$ be a divisor of $k$. Can you show that $(1+p)\Bigl(1+\dfrac kp\Bigr)$ is divisible by $3$ and by $8$?

Thanks for the hint:

I´m not sure. Here is my attempt:

If $p < \sqrt{k}$ and $k \equiv 0 \:\: (mod \:\: p)$ then $k+1 \equiv 0 \:\: (mod \:\: p+1)$

$\Rightarrow$ $p+1 \equiv 0 \:\: (mod \:\: 3)??$

but it is not necessarily true, that: $k+1 \equiv 0 \:\: (mod \:\: 1+\frac{k}{p}).$

For example: Say $k = 95$, then $k \equiv 0 \:\: (mod \:\: p=5)$ and $k+1=96 \equiv 0 \:\: (mod \:\: p+1=6)$

- but $\frac{k}{p}=\frac{95}{5}=19$ and $k+1=96 \not\equiv 0 \:\: (mod \:\: p+1=20)$

Still it is true, that $3$ and $8$ divides $96$. I just don´t know how to prove this ... :(

If I could show, that $3$ and $8$ divides $(1+p)(1+\frac{k}{p})$ then $k+1 + p + \frac{k}{p}$ would of course also
be divisible by $24$, that is $p +\frac{k}{p}$ would be divisible by 24 as required.
 
  • #4
For convenience, write $q = \dfrac kp$, so that $k = pq$. You know that $k\equiv-1\pmod3$. As you say, it does not necessarily follow that $p\equiv-1\pmod3$. But the only way that the product of two integers can be congruent to $-1\pmod3$ is that one of them is $\equiv1\pmod3$ and the other one is $\equiv-1\pmod3.$ So what is true is that either $p+1$ or $q+1$ must be a multiple of $3$.

A similar argument working mod $4$ shows that one of the integers $p+1,\,q+1$ is a multiple of $2$ and the other one is a multiple of $4$.
 
  • #5
Opalg said:
For convenience, write $q = \dfrac kp$, so that $k = pq$. You know that $k\equiv-1\pmod3$. As you say, it does not necessarily follow that $p\equiv-1\pmod3$. But the only way that the product of two integers can be congruent to $-1\pmod3$ is that one of them is $\equiv1\pmod3$ and the other one is $\equiv-1\pmod3.$ So what is true is that either $p+1$ or $q+1$ must be a multiple of $3$.

A similar argument working mod $4$ shows that one of the integers $p+1,\,q+1$ is a multiple of $2$ and the other one is a multiple of $4$.

Thanks a lot, Opalg! This really helped me solve the matter!
 

FAQ: Why is $p_i + \frac{k}{p_i}$ divisible by $3$ and $8$?

1. What is the Sum of Divisors problem?

The Sum of Divisors problem is a mathematical problem that asks you to find the sum of all the divisors of a given number. This means finding all the numbers that can divide the given number without leaving a remainder, and then adding them all together.

2. Why is the Sum of Divisors problem important?

The Sum of Divisors problem has many applications in mathematics and computer science. It is used in number theory and has applications in cryptography and coding theory. It can also be used to solve other mathematical problems, such as finding perfect numbers.

3. How is the Sum of Divisors problem solved?

The most common method for solving the Sum of Divisors problem is to factor the given number into its prime factors. Then, using the formula for the sum of divisors, the sum can be calculated by multiplying the prime factors together and adding 1 to each exponent, and then multiplying all of these numbers together.

4. Can the Sum of Divisors problem be solved for any number?

Yes, the Sum of Divisors problem can be solved for any positive integer. However, for very large numbers, it may be computationally intensive to find all the divisors and add them together.

5. Are there any other methods for solving the Sum of Divisors problem?

Yes, there are other methods for solving the Sum of Divisors problem, such as using a sieve algorithm or using the Möbius function. These methods may be more efficient for certain types of numbers, but they are more complex and require a deeper understanding of number theory.

Back
Top