2
$\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$
5
  • $\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$ Nov 3, 2016 at 16:59
  • $\begingroup$ @arberavdullahu You forgot 1 as a divisor. The sum is squarefree. $\endgroup$ Nov 3, 2016 at 17:01
  • $\begingroup$ @Alephnull yes you're right, thank you. $\endgroup$ Nov 3, 2016 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, 2016 at 17:03
  • $\begingroup$ Thanks @lulu. That clears it up. $\endgroup$
    – superckl
    Nov 3, 2016 at 17:15

1 Answer 1

-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$
5
  • $\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, 2016 at 3:33
  • $\begingroup$ U still don't have a proof ? I do but won't post until class $\endgroup$
    – Randin
    Nov 6, 2016 at 3:35
  • $\begingroup$ That was a hint to help u prove it $\endgroup$
    – Randin
    Nov 6, 2016 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, 2016 at 3:37
  • $\begingroup$ His link proves the case for prime powers of 2 . Bogus American uw droid $\endgroup$
    – Randin
    Nov 9, 2016 at 23:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .