# $2^{61}$ as a multiple of 3… is that possible?

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.

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

## 4 Answers

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$.

The reason is

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

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

My own answer

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

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

• 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) – RikkiTikkiTavi Apr 11 '16 at 14:53