Is the following true, for each positive integer ## k ##?

In summary, the conversation discussed the topic of time management and the strategies that can be used to improve it. The participants shared their personal experiences and tips, such as setting priorities, creating a schedule, and avoiding distractions. They also emphasized the importance of self-discipline and motivation in managing time effectively. Overall, it was concluded that with the right techniques and mindset, anyone can become better at managing their time.
  • #1
Math100
801
221
Homework Statement
Is the following true, for each positive integer ## k ##?
## 5\mid \sigma_{1} (5k+4) ##
Briefly justify your answer.
Relevant Equations
None.
Let ## 5k+4=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}} ##.
Then ## 5\equiv 0\pmod {5} ## and ## 5k+4\equiv 4\pmod {5} ##.
Thus ## p_{i}^{k_{i}}\not \equiv 0\pmod {5} ## for ## i=1, 2,..., s ##.
Suppose all ## p_{i}^{k_{i}}\equiv 1\pmod {5} ##.
Then ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 1\pmod {5} ##.
Since ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 4\pmod {5} ##,
it follows that ## \exists ## one ## p_{i} ## satisfying ## p_{i}^{k_{i}}\equiv 4\pmod {5} ##.
This means ## p_{i}\equiv 4\pmod {5} ##.
Observe that ## p_{i}^{2}\equiv 16\equiv 1\pmod {5} ## and ## p_{i}^{3}\equiv 4\pmod {5} ##.
If ## p_{i}^{r}\equiv 4\pmod {5} ##, then ## r ## must be odd.
This implies ## p_{i}^{k_{i}}\equiv 4\pmod {5} ## where ## k_{i} ## is odd.
Now we have
\begin{align*}
&\sigma_{1} (p_{i}^{k_{i}})=p_{i}^{k_{i}}+p_{i}^{k_{i}-1}+\dotsb +p_{i}+1\\
&\equiv (4+1+\dotsb +4+1)\pmod {5}\\
&\equiv 0\pmod {5},\\
\end{align*}
because ## p_{i}^{r}\equiv 4\pmod {5} ## if ## r ## is odd and ## p_{i}^{r}\equiv 1\pmod {5} ## if ## r ## is even.
Thus
\begin{align*}
&5\mid \sigma_{1} (p_{i}^{k_{i}})\implies 5\mid [\sigma_{1} (p_{1}^{k_{1}})\dotsb \sigma_{1} (p_{i}^{k_{i}})\dotsb \sigma_{1} (p_{s}^{k_{s}})]\\
&\implies \sigma_{1} (p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}).\\
\end{align*}
Therefore, ## 5\mid \sigma_{1} (5k+4) ## for each positive integer ## k ##. And the following is true.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: Is the following true, for each positive integer ## k ##?
## 5\mid \sigma_{1} (5k+4) ##
Briefly justify your answer.
Relevant Equations:: None.

Let ## 5k+4=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}} ##.
Then ## 5\equiv 0\pmod {5} ## and ## 5k+4\equiv 4\pmod {5} ##.
Thus ## p_{i}^{k_{i}}\not \equiv 0\pmod {5} ## for ## i=1, 2,..., s ##.
Suppose all ## p_{i}^{k_{i}}\equiv 1\pmod {5} ##.
Then ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 1\pmod {5} ##.
Since ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 4\pmod {5} ##,
it follows that ## \exists ## one ## p_{i} ## satisfying ## p_{i}^{k_{i}}\equiv 4\pmod {5} ##.
What about ##p_1,p_2\equiv 2\pmod{5}##?
 
  • #3
fresh_42 said:
What about ##p_1,p_2\equiv 2\pmod{5}##?
I am not sure. How did you get ## p_{1}, p_{2}\equiv 2\pmod {5} ##?
 
  • #4
You said, that there must be a prime factor congruent ##4## modulo ##5##. However, you did not cover the case ##2\cdot 2=4.## Assume ##5k+4=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}.## What if ##p_1^{k_1}\equiv 2\pmod{5}## and ##p_2^{k_2}\equiv 2\pmod{5}##? E.g. consider ##n=14.##
 
  • #5
fresh_42 said:
You said, that there must be a prime factor congruent ##4## modulo ##5##. However, you did not cover the case ##2\cdot 2=4.## Assume ##5k+4=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}.## What if ##p_1^{k_1}\equiv 2\pmod{5}## and ##p_2^{k_2}\equiv 2\pmod{5}##? E.g. consider ##n=14.##
If ## p_{1}^{k_{1}}\equiv 2\pmod {5}, p_{2}^{k_{2}}\equiv 2\pmod {5} ##, then ## p_{1}^{k_{1}}p_{2}^{k_{2}}\equiv 4\pmod {5}.## You said to consider ## n=14 ##, but where does ## n=14 ## come from?
 
  • #6
Math100 said:
If ## p_{1}^{k_{1}}\equiv 2\pmod {5}, p_{2}^{k_{2}}\equiv 2\pmod {5} ##, then ## p_{1}^{k_{1}}p_{2}^{k_{2}}\equiv 4\pmod {5}.## You said to consider ## n=14 ##, but where does ## n=14 ## come from?
It is an example of why your proof does not work. ##14=2\cdot 5 +4## but no prime divisor or its power is congruent ##4## modulo ##5.##
 
  • #7
fresh_42 said:
It is an example of why your proof does not work. ##14=2\cdot 5 +4## but no prime divisor or its power is congruent ##4## modulo ##5.##
Then how should I disprove this? By using one of the counterexample(s) you've provided above?
 
  • #8
I haven't provided any counterexamples. I just said why your proof cannot work. Have you calculated ##\sigma_1(14)?##
 
  • #9
fresh_42 said:
I haven't provided any counterexamples. I just said why your proof cannot work. Have you calculated ##\sigma_1(14)?##
No. What's ##\sigma_1(14)?##
 
  • #10
Math100 said:
No. What's ##\sigma_1(14)?##
Do you know what ##\sigma_1## means?
 
  • #11
fresh_42 said:
Do you know what ##\sigma_1## means?
No, what does it mean?
 
  • #12
Math100 said:
No, what does it mean?
It is the function that adds all divisors. So ##\sigma_1(14)=1+2+7+14=24## and ##5\,\nmid\, 24.##
 
  • #13
fresh_42 said:
It is the function that adds all divisors. So ##\sigma_1(14)=1+2+7+14=24## and ##5\,\nmid\, 24.##
I thought it's only the ## \sigma(n) ##, not the ## \sigma_{1}(n) ##.
 
  • #14
So ## \sigma_{1}(n) ## is the sum of all n's divisors.
 
  • #15
Math100 said:
I thought it's only the ## \sigma(n) ##, not the ## \sigma_{1}(n) ##.
This would be a matter of convention. Your problem used the function ##\sigma_1## so you must know what it means. In general, we have ##\sigma_k(n)=\sum_{d|n} d^k.##
Math100 said:
So ## \sigma_{1}(n) ## is the sum of all n's divisors.
Yes. For ##k=1## we get ##\sigma_1(n)=\sum_{d|n} d^1=\sum_{d|n}.##
 
  • #16
Now I know that ## 5\mid \sigma_{1} (5k+4) ## isn't true for each positive integer ## k ##, because we just tested ## k=2 ##.
 
  • Like
Likes fresh_42
  • #17
Math100 said:
Now I know that ## 5\mid \sigma_{1} (5k+4) ## isn't true for each positive integer ## k ##, because we just tested ## k=2 ##.
Yes. The statement is false.
 
  • Like
Likes Math100
  • #18
fresh_42 said:
This would be a matter of convention. Your problem used the function ##\sigma_1## so you must know what it means. In general, we have ##\sigma_k(n)=\sum_{d|n} d^k.##

Yes. For ##k=1## we get ##\sigma_1(n)=\sum_{d|n} d^1=\sum_{d|n}.##
Then how should I disprove this statement? By letting ## k=2 ## as a counterexample?
 
  • #19
Math100 said:
Then how should I disprove this statement? By letting ## k=2 ## as a counterexample?
Yes, for example. Maybe you can find a second one.
 
  • #20
Disproof:

Here is a counterexample:
Let ## k=6 ##.
Then ## \sigma_{1} (34)=1+2+17+34=54 ##.
Note that ## 5\nmid 54 ##.
Therefore, ## 5\nmid \sigma_{1} (5k+4) ## for each positive integer ## k ##. And the following statement is false.
 
  • Like
Likes fresh_42

FAQ: Is the following true, for each positive integer ## k ##?

What is the definition of a positive integer?

A positive integer is a whole number that is greater than zero. It can be written without a fractional or decimal component.

Is zero considered a positive integer?

No, zero is not considered a positive integer. It is a whole number, but it is neither positive nor negative.

Can a positive integer be a fraction or decimal?

No, a positive integer must be a whole number. Fractions and decimals are not considered positive integers.

What is the difference between a positive integer and a negative integer?

A positive integer is a whole number that is greater than zero, while a negative integer is a whole number that is less than zero. They are on opposite sides of the number line.

Can a positive integer be a prime number?

Yes, a positive integer can be a prime number. A prime number is a positive integer that is only divisible by 1 and itself.

Back
Top