Solving an Exponential Diophantine Equation

This video is about solving an Exponential Diophantine Equation
If you need to post a picture of your solution or idea:
#NumberTheoryProblems #DiophantineEquations

EXPLORE:

[engjayah]

Another approach.
1984 = 2^6.31;
Divide both sides by 2^6 and rearranging terms we get
2^(x-6) - 2^(y-6) = 31;
Now the powers of 2 will never become odd unless one of the terms is equal to one!
Hence, 31 = 32 - 1; meantime we are aware that x > y as RHS is a positive number;
Hence, y-6 = 0 and x-6 = 5
From which we deduce x = 11 and y = 6

[angelmendez-rivera]

In my view, the key to solving this is to understand how binary expansions work. We are used to working with decimal expansions, but any decimal expansion can be converted to a binary expansion. For example, rather than writing 1984 as 10^3 + 9·10^2 + 8·10 + 4, I can write it using sums of powers of 2. For example, notice that 2^10 = 1024, and 1984 – 1024 = 960, so 1984 = 2^10 + 960. Also, 2^9 = 512, and 960 – 512 = 448, so 960 = 2^9 + 448, and 1984 = 2^10 + 2^9 + 448. Similarly, 2^8 = 256, and 448 – 256 = 442 – 250 = 242 – 50 = 192, so 448 = 2^8 + 192, and 1984 = 2^10 + 2^9 + 2^8 + 192. 2^7 = 128, and 192 – 128 = 72 – 8 = 64 = 2^6, so 192 = 2^7 + 2^6. Therefore, 1984 = 2^10 + 2^9 + 2^8 + 2^7 + 2^6.

Why do we care about this binary expansion? Because we can rewrite the Diophantune equation as 2^x = 2^10 + 2^9 + 2^8 + 2^7 + 2^6 + 2^y. Notice how, because binary expansions work analogously to decimal expansions, the only way to make the sum collapse into a single exponential is if 2^y = 2^6, so that each rising term doubles. This is analogous to how, if I have a sum of powers of 10, the only hope to collapse them is if the coefficients of the power add to 9, and this may require that one of the powers being added have the same exponent. For example, if I had 9·10^11 + 10^y and I needed this to collapse into a power of 10, the only possibility is by adding 1 to the 9, by letting 10^y = 10^11. The same principle applies in binary expansions, or for expansions in any base, really. Therefore, 2^6 = 2^y, so y = 6. So 2^x = 2^10 + 2^9 + 2^8 + 2^7 + 2^6 + 2^6 = 2^10 + 2^9 + 2^8 + 2^7 + 2·2^6 = 2^10 + 2^9 + 2^8 + 2^7 + 2^7 = 2^10 + 2^9 + 2^8 + 2^8 = 2^10 + 2^9 + 2^9 = 2^10 + 2^10 = 2^11. So 2^x = 2^11, so x = 11. Therefore, the only solution to this equation is (x, y) = (11, 6).

[devondevon]

Great channel, I like the effort you put in to explain the problem.

[princepradhan]

THANK YOU SIR FOR THIS GREAT EXPLAINATION

[ruggbi]

Will you be doing Olympiad problems? I like the way you explain. Good video!

[Rudxain]

I'm a programmer, and I once coded a very efficient GCD finder using a "mix" of the best 3 algorithms known (Euclidean with modulo, Stein's Binary variant, and Lehmer's standard), so I learned that if a Mersenne number is appended trailing zeros, its GCD can be found as efficiently as if it didn't have trailing zeros. I also know that subtracting different powers of 2 results in a Mersenne numeral with an amount of trailing zeros equal to the number of TZs in the smaller power (right side of the minus), while the whole size of the result is equal to the number of TZs in the larger power.

Example (written in binary): 1000 - 10 = 110. So to find which exponents satisfy the equation, just compute ilb(x) (integer binary logarithm of x) and CTZ(x). The logarithm plus 1 gives you the greater exponent, the CTZ gives you the smaller exponent. In the case of 1984, it's ilb(1984) = 10, ctz(1984) = 6

[an_ricko]

I want to show my solution. 1984 can be represented in binary. We get Let's represent it as a difference of numbers with one "1": - Which corresponds to 2^11 - 2^6 in decimal system.

[arden]

I tried the problem on my own and could solve it! I wrote 1984 as 2^6 x 31 and then wrote it has 2^6 (2^5 - 1) thus getting 2^11 - 2^6 after that I just compared and got x = 11 and y = 6.
lately I have been loving watching your videos!

[DilipKumar-nskl]

Expressing 1984 as sum of powers of 2
We get
2^x-2^y = 2^10 + 2^9 + 2^8 + 2^7 + 2^6
We may write,
2^x= 2^10+2^9+2^8+2^7+2^6+2^y
As every number can be presented in only one way as sum of powers of 2,
the RHs can be squeezed to a single power of 2 (as in LHS) in only one way,
2^6+2^y must be equal to 2^7.
Then RHS squeezes to 2^11
Hence x is 11 & y is 6.

[ezzatabdo]

Excellent nice and also beautiful, thanks sir.

[RexxSchneider]

The key to solving any of these sort of exponential Diophantines is to change the difference on the RHS into a product. Next you see that 1984 divides by 8 (100 is congruent to 4 mod 8 and 84 is congruent to 4 mod 8), and it's then quick to see the prime factorisation of 1984 is 2^6 x 31. So the product on the RHS has to contain 31 as a factor if there are any solutions.

In general, you go about solving anything of the form n^x - n^y = m by changing it into n^y(n^(x-y) - 1) = m and considering the prime factorisation of m.

[-basicmaths]

Second method
x>y
x=y+k
2^y+k -2^y=64*31
2^y(2^k -1)=64*31
2^y=64, 2^k -1=31
y=6, 2^k=32
y=6, y+k=x=11

[CriticSimon]

This is a great problem! Thank you for the video. I'm looking forward to the geometry puzzle 😍

[Sarif_boy_amit_]

Thanks a lot sir
At first moment I decided to cut the video but when I went through the video I realised 👍👍👍👍👍👍👍👍👍👍👍

[nicks]

2^x - 2^y = 1984. 2^n is strictly increasing so x > y and since they’re both integers x >= y+1 or x-1>= y and 2^(x-1) >= 2^y

2^x - 2^(x-1) <= 1984
2^(x-1) <= 1984
x-1 <= 10 (since x is an integer)
x <= 11

2^x = 2^y + 1984. Since for all real numbers 2^y > 0 we can say:
2^x > 1984 so x>10

10<x<=11 so x = 11

Solve for y

2^y = 2^11-1984,
y = 6

[rayaneblii]

I'm in lobe with u'r videos 🔥❤⚡

[spiderjerusalem]

any tips for people like me who loathe number theory? Btw, all i did was find out 2 to the power whatever so that the result would be bigger than 1984, which is 2084, then

2ˣ – 2ʸ = 2048 – 64 = 2¹¹ – 2⁶
x = 11
y = 6

[rtdavis]

Using the subtraction algorithm learned in elementary school, you find that a positive number is the difference of powers of 2 if and only if its binary expansion looks like 1...10...0 (some number of 1's followed by some number of 0's). And 1984 = = 2^11 - 2^6.

[-basicmaths]

Add 64 both sides of the equation.
2^x- 2^y+64=1984+64=2048
2^x- 2^y+2^6=2^11
2^x- 2^y=2^11- 2^6
x=11, and y=6

[mangeshbhanage]

If we look at 1984. The nearest power of 2 is 2048= 2^11
2048-1984 = 64 = 2^6
2048- 64 = 2^11 - 2^6 . Hence x= 11 y =6