Knowing your A, B and Cs

Number Theory Level 4

How many solutions for non-negative integers $(a,b,c)$ are there to the equation below?

$2^a+2^b= c!$

Notation: $!$ is the factorial notation. For example, $8! = 1\times2\times3\times\cdots\times8$ .

6 0 2 3 4 5

2 solutions

Zee Ell
Nov 20, 2016

Due to symmetry, we can premise, that a ≤ b.

Then we can write our equation in the following form:

$2^a ( 2^{b - a} + 1) = c!$

Now, we will show, that the LHS is not divisible by 7, hence c < 7 (otherwise 7 would be a factor of the RHS which leads us to a contradiction):

If the expression would be divisible by 7, it would mean that the second term (in the brackets) has to be divisible by 7 as an integral power of 2 (the first term of the LHS) cannot have a factor of 7.

However, the powers of 2 always give the remainders (when divided by 7) in the following cycle: 1, 2, 4, 1, 2, 4, ... ; therefore our bracketed expression follows the cycle 2, 3, 5, 2, 3, 5... (remainder is never 0), so the LHS is not divisible by 7.

At this point, we only have to evaluate the following set of c values:

{0, 1, 2, 3, 4, 5, 6}

It is easy to see that we have a minimum value of 2 (a=b=0) for the LHS, therefore no solution for c = 0 or c = 1 (as 0! = 1! = 1)

For c = 2, we have 1 solution:

$2^0 + 2^0 = 2! = 2$

For c = 3, we have 2 solutions (due to symmetry):

$2^1 + 2^2 = 3! = 6$

$2^2 + 2^1 = 3! = 6$

For c = 4, we have another 2 solutions (due to symmetry):

$2^4 + 2^3 = 4! = 24$

$2^3 + 2^4 = 4! = 24$

For c = 5, we have no solution:

$2^a ( 2^{b - a} + 1) = 5! = 120$

$2^a ( 2^{b - a} + 1) = 2^3 × 15$

Since the bracketed second term is not divisible by 2, and the first term has the only factor of 2, therefore:

$2^{b - a} + 1 = 15$

And now it is easy to see, that we don't have an integral solution of the following equation:

$2^{b - a} = 14$

For c = 6 (similarly to the c=5 case), we have no solution, either:

$6! = 720 = 2^4 × 45$

and there is no integral solution of the equation:

$2^{b - a} = 45$

$\text {Hence, we have the following } \boxed {5} \text { (a, b, c) triplets as solutions: }$

(0, 0, 2), (1, 2, 3), (2, 1, 3), (3, 4, 4) and (4, 3, 4).

Very nice solution, got my vote and Thank you.

Hana Wehbi - 4 years, 6 months ago

I was actually correct...but symmetricity is something which I have not considered

Swayam Prakash Kar - 1 year, 7 months ago

You can sharpen the bound to $c\leq 4$ .

Proof. Let us assume that there exists solutions for $c\geq 5$ . WLOG, we can consider $a\leq b$ due to symmetry. Now, we have,

$2^a(2^{b-a}+1)=c!$

Since $c\geq 5$ , $c!$ is divisible by both $3$ and $5$ and so is $2^a(2^{b-a}+1)$ . Since $\gcd(2,3)=\gcd(2,5)=1$ , we must have that $2^{b-a}+1$ is divisible by both $3$ and $5$ . So,

$3\mid 2^{b-a}+1\iff 2^{b-a}\equiv -1\equiv 2\pmod{3}\overset{\gcd(2,3)=1}{\iff} 2^{b-a-1}\equiv 1\pmod{3}\qquad(*)$

$5\mid 2^{b-a}+1\iff 2^{b-a}\equiv -1\equiv 4\pmod{5}\overset{\gcd(2,5)=1}{\iff} 2^{b-a-2}\equiv 1\pmod{5}\qquad(**)$

From the equations $(*)$ and $(**)$ , using the generalized version of Fermat's Little Theorem, we have $b-a\equiv 1\pmod{2}$ and $b-a\equiv 2\pmod{4}$ .

But note that $b-a\equiv 1\pmod{2}$ implies that $b-a$ is odd whereas $b-a\equiv 2\pmod{4}$ implies that $b-a$ is even, which is a contradiction.

So, our initial assumption that there exists solutions for $c\geq 5$ is wrong. Hence, we must have $c\leq 4$ for solutions to exist.

Prasun Biswas - 4 years, 6 months ago

A way to speed up the case checking is to write the factorials in binary - if there is one 1 involved, that leads to a solution, if there are two 1s involved, that leads to two solutions.

Yong See Foo - 4 years, 6 months ago

Sir, what motivated you to choose $7$ and not $3$ or $5$ and or some other number ?

Aditya Sky - 4 years, 1 month ago

Hana Wehbi
Nov 23, 2016

This is not a complete solution, just another idea of how to approach it.

We can check that $2^a + 2^b$ is never divisible by $7$ , so we must have $c < 7$ . The binary representation of $2^a + 2^b$ has at most two $1’s$ .

Writing $0!, 1!, 2!, . . . , 6!$ in binary, we can check that the only possibilities are $c = 2, 3, 4$ , giving solutions $(0, 0, 2), (1, 2, 3), (2, 1, 3), (3, 4, 4), (4, 3, 4)$ .

Knowing your A, B and Cs

2 solutions

0 pending reports