1
$\begingroup$

We were given this question on one of our recent exams, and we can't seem to generate a proof, nor find a counter-example.

If we let $\sigma(n)$ be the sum of the divisors of $n$, the question is, if

$$\sigma(n)=2^k$$

for some $k$, does this imply $n$ is square free?

This is clearly true if we consider just the number of divisors being a power of two, but we cannot extend it to the sum of the divisors. We have tried numerous $n$ that are not square-free, and none have given a counter-example. We made some progress in noting that if

$$n=p_1^{k_1}p_2^{k_2}...p_j^{k_j}$$

is the prime factorization of $n$, then

$$2^k=\sigma(n)=(1+p_1+p_1^2+...+p_1^{k_1})...(1+p_j+p_j^2+...+p_j^{k_j})$$

This then implies that each factor must be a power of two itself, and thus for each $p_i$,

$$p_i+p_i^2+...+p_i^{k_i}=2^t-1$$

for some $t$. Even with this, we are unable to find a counter-example. There does not seem to be a non-trivial solution.

Is there a proof we can't see, or is there a counter-example we can't find?

EDIT: From a comment by @lulu $\sigma(n)=2^k$ when $n$ is a product of distinct Mersenne primes, and is thus square-free. Since we have not covered these in our class, I'm still open to other solutions.

$\endgroup$
  • $\begingroup$ If we take n=$2^n$ then its sum of divisor is $2^{n+1}$ but $2^n$ isn't square free for $n\geq 2$. Perhaps problem is when n is odd $\endgroup$ – arberavdullahu Nov 3 '16 at 16:59
  • $\begingroup$ @arberavdullahu You forgot 1 as a divisor. The sum is squarefree. $\endgroup$ – Jacob Wakem Nov 3 '16 at 17:01
  • $\begingroup$ @Alephnull yes you're right, thank you. $\endgroup$ – arberavdullahu Nov 3 '16 at 17:02
  • 1
    $\begingroup$ this question is relevant. the only such $n$ are products of distinct Mersenne primes (hence square free). $\endgroup$ – lulu Nov 3 '16 at 17:03
  • $\begingroup$ Thanks @lulu. That clears it up. $\endgroup$ – superckl Nov 3 '16 at 17:15
-1
$\begingroup$

Mersenne prime is a prime number that can be written in the form Mn = 2^n − 1 for some integer  n. mersenne numbers are all integers of that same form including the ones that fail primality test .

$\endgroup$
  • $\begingroup$ I know what a Mersenne prime is, but a proof involving them wasn't covered in the course. I asked for an alternative proof. $\endgroup$ – superckl Nov 6 '16 at 3:33
  • $\begingroup$ U still don't have a proof ? I do but won't post until class $\endgroup$ – Randin Nov 6 '16 at 3:35
  • $\begingroup$ That was a hint to help u prove it $\endgroup$ – Randin Nov 6 '16 at 3:35
  • $\begingroup$ The link from @Lulu has a relevant question that essentially proves this using Mersenne primes. I feel that's probably the only way, but I'm curious for an alternate proof. $\endgroup$ – superckl Nov 6 '16 at 3:37
  • $\begingroup$ His link proves the case for prime powers of 2 . Bogus American uw droid $\endgroup$ – Randin Nov 9 '16 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.