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

[lfdahl]

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!

 

[Opalg]

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$?

 

[lfdahl]

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.

 

[Opalg]

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

 

[lfdahl]

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!