3
$\begingroup$

I had a recent conversation with a friend of mine who said that $2^{61}$ was a multiple of 3, but I wanted to disprove this argument by claiming that all values of $2^n$ were not a multiple of 3 at all, and that it was impossible for such a claim to exist.

Is $2^{61}$ a multiple of 3 and why?

Thanks.

$\endgroup$
  • 11
    $\begingroup$ No, it is not. Unique Factorization $\endgroup$ – lulu Apr 11 '16 at 14:37
  • 3
    $\begingroup$ $2^{61}$ divisible only by numbers $2^{k}$, where $0\le k \le 61$ $\endgroup$ – Roman83 Apr 11 '16 at 14:40
  • 2
    $\begingroup$ $2^{61}+1=2^{61}+1^{61}=(2+1)(2^{60}-\dots)$ is a multiple of $3$, hence $2^{61}$ isn't. $\endgroup$ – Wojowu Apr 11 '16 at 14:40
  • $\begingroup$ @Wojowu hmm, how did you get $2^{61} + 1^{61}$? Can you post as a solution please? $\endgroup$ – vik1245 Apr 11 '16 at 14:42
  • 1
    $\begingroup$ @BobSmith $1=1^{61}$ $\endgroup$ – user228113 Apr 11 '16 at 14:59
5
$\begingroup$

What lulu commented: Every integer can be uniquely separated into a multiplication of primes called a "factorization" (which is just the number itself, if it is a prime). The integer is only divisible by the primes that are part of the factorization. $2^n$ means that the factorization is $2\cdot2\cdot2\cdot2\cdot2\cdot...$ . Hence the number is divisible by no other prime than $2$.

$\endgroup$
5
$\begingroup$

The reason is

$$ 2 \ \mathrm{mod}\ 3 = -1 \implies 2^n \ \mathrm{mod}\ 3= (-1)^n=-1 \text{ or } 1 = 2 \text{ or } 1 $$

$\endgroup$
3
$\begingroup$

No $2^n$ is not divisible by 3 as it does not contains any factor of $3$

So $2^{61}$ is not divisible by 3

$\endgroup$
0
$\begingroup$

My own answer

$2^{61} = 2 * 2* 2* 2... (61 \ times)$

There is no factor of 3, so this is impossible.

$\endgroup$
  • 1
    $\begingroup$ If factorization wasn't unique it could still be divisible by 3. But factorization is unique, so this is the reason, yes. (meaning that there is only one factorization for each integer) $\endgroup$ – RikkiTikkiTavi Apr 11 '16 at 14:53

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.