Help with 3 proofs (integers/diophantine equations)

[firefly767]

this might be answered already, but i didnt find a detailed proof... so here it goes:

1. an integer n is perfect if the sum of its divisors including 1 and itself is 2n. show that if 2^p-1 is a prime number, then n=2^(p-1) (2^p -1) is perfect.

2. show that 1+ 1/2 + 1/3 +... +1/n can never be an integer if n>1.

3. if [x] is the greatest integer less than or equal to x, then for which values of n does [sqrt n] divide n?

 

[disregardthat]

1. What are the divisors of n = 2^{p-1}(2^p-1)? Remember that 2^p-1 is a prime number, so the possibilities are easy to spot. Now sum them up.

2. Hm, there are probably easier ways to do this, but my suggestion is to look at the largest prime factor among 1,2,3,...,n. By Bertrands postulate it only occurs once. See what you can do with that. Hint: Multiply both sides with n!.

3. Write n = k^2 + r, where k^2 is the largest square less than or equal to n. What is \lfloor \sqrt{n} \rfloor? How many possibilities are there for r? Note that k^2+2k+1=(k+1)^2+0, so r < 2k+1.

 

[Raphie]

1. What are the divisors of n = 2^{p-1}(2^p-1)? Remember that 2^p-1 is a prime number, so the possibilities are easy to spot. Now sum them up.

For a "demonstration" of what Jarle is saying here, see the following thread...
https://www.physicsforums.com/showthread.php?t=448993

And also note that 2^{p-1}(2^p-1) follows the form n*(2n -1) which is another way of phrasing the formula for an odd-number indexed triangular number (e.g. 5 * 9 = 45 = T_9; 16 * 31 = 496 = T_31), otherwise referred to as a "hexagonal" number.

 

[firefly767]

thanks for the tips guys!

for Q.1 i have arrived at the result of proving that 2^0+2^1+2^3+2^...2^(p-1) = 2^p - 1 i tried couple numbers and it is true... but how do i go about doing that? : <

 

[disregardthat]

As you know 2^k for k < p are factors. What about 2^k(2^p-1) ? Can there be more?

EDIT: Or did you mean that you have showed the result given that 2^0+2^1+...+2^(p-1) = 2^p-1? In that case note that this is a geometric series for which there is a well-known formula.

 

[robert Ihnot]

(2) Is a standard number theory problem. The usual approach is to look at powers of 2, and use n!.

 

[robert Ihnot]

What we have here for 2) is the form: \sum{\frac{\frac {N!}{n_i}}{N!}}}, where we both multiply and divide by N!.

Now it is an interesting and seldom mention property of 2, that is is the only case in a successive series of integers, where the highest power always occurs only once. For example, if 2^n occurs in this series, where is the next such case in the set 2^n+x? Well, x has to go to 2^n, but in that case, we have 2^n+2^n = 2^(n+1), so that the next case of 2^n comes at 2^(n+1)+2^n, but then we have already found a higher power!

So in the set of integers from 1 to N, there is one case of 2^r, which is the highest power of 2 in the term 1/n(i). Say N! has p cases of power of 2, then 2^r divides out in N! at that point, to leave 2^(p-r) in the numerator at that term, HOWEVER, every other term contains 2 to a higher power, so once 2^(p-r) is factored out of all the numerator, IT LEAVES A SINGLE TERM THAT DOES NOT CONTAIN 2.

This power of 2 can be divided out by the denominator, N!, leaving an even term contain 2^r, and thus the numerator is odd and the denominator is even, so it cannot be an integer!