Find the remainder

Is 8 2048 6 2048 8^{2048}-6^{2048} divisible by 700?

Can't tell Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Chew-Seong Cheong
Mar 10, 2017

8 2048 6 2048 = ( 8 1024 6 1024 ) ( 8 1024 + 6 1024 ) (mod 700) = ( 8 512 6 512 ) ( 8 512 + 6 512 ) ( 8 1024 + 6 1024 ) (mod 700) = ( 8 256 6 256 ) ( 8 256 + 6 256 ) ( 8 512 + 6 512 ) ( 8 1024 + 6 1024 ) (mod 700) = ( 8 6 ) ( 8 + 6 ) ( 8 2 + 6 2 ) ( 8 3 + 6 3 ) . . . ( 8 1024 + 6 1024 ) (mod 700) = ( 2 ) ( 14 ) ( 100 ) ( 8 3 + 6 3 ) . . . ( 8 1024 + 6 1024 ) (mod 700) = 0 (mod 700) \begin{aligned} 8^{2048}-6^{2048} & = (8^{1024}-6^{1024})(8^{1024}+6^{1024}) \text{ (mod 700)} \\ & = (8^{512}-6^{512})(8^{512}+6^{512})(8^{1024}+6^{1024}) \text{ (mod 700)} \\ & = (8^{256}-6^{256})(8^{256}+6^{256})(8^{512}+6^{512})(8^{1024}+6^{1024}) \text{ (mod 700)} \\ & = (8-6)(8+6)(8^2+6^2) (8^3+6^3)...(8^{1024}+6^{1024}) \text{ (mod 700)} \\ & = (2){\color{#3D99F6}(14)(100)} (8^3+6^3)...(8^{1024}+6^{1024}) \text{ (mod 700)} \\ & = {\color{#3D99F6}\boxed{0}} \text{ (mod 700)} \end{aligned}

Yes , 8 2048 6 2048 8^{2048}-6^{2048} is divisible by 700.

How do you prove it is divisible by 100 as well?

Freddie Hand - 4 years, 3 months ago

who will prove it divisible by 100??

Nivedit Jain - 4 years, 3 months ago

Log in to reply

The original problem I read was only divisible by 7. See Vicky Vignesh's solution.

Chew-Seong Cheong - 4 years, 3 months ago

Log in to reply

i have solved it before him

Nivedit Jain - 4 years, 3 months ago

Log in to reply

@Nivedit Jain I solved it earlier but did not provide solution. I only provided solution after seeing her solution. I didn't see any other solution. I have provided the solution for divisible by 700.

Chew-Seong Cheong - 4 years, 3 months ago

Log in to reply

@Chew-Seong Cheong i know sir i just commented that in fun

Nivedit Jain - 4 years, 3 months ago

Log in to reply

@Nivedit Jain It is quite okay. We all are serious about math.

Chew-Seong Cheong - 4 years, 3 months ago

I have provided a new solution.

Chew-Seong Cheong - 4 years, 3 months ago

oh! awesome one

Nivedit Jain - 4 years, 3 months ago
Jia En
Apr 10, 2017

Apply the formula a^2n - b^2n = (a^n - b^n) (a^n + b^n) repeatedly until the power of 8 and 6 is 1. 2048 = 2^20.

8^2048 - 6^2048 = (8^1024 - 6^1024) * (8^1024 +6^1024) = (8^516 - 6^516) * (8^516 + 6^516) * (8^1024 +6^1024) = (8^256 - 6^256) * (8^256 - 6^256) *(8^516 + 6^516) * (8^1024 +6^1024) ..... = (8^2 - 6^2) * (8^2 +6^2) * ... * (8^256 - 6^256) *(8^516 + 6^516) * (8^1024 +6^1024) = (8 - 6) * (8 + 6) * (8^2 +6^2) * ... * (8^256 - 6^256) *(8^516 + 6^516) * (8^1024 +6^1024)

8+6 =14 (8^2 +6^2) = 64 + 36 = 100

2, 7, 100 are factors of 8^2048 - 6^2048 Therefore 700 divides 8^2048 - 6^2048

We have:

8 2048 6 2048 0 2 2048 3 2048 4 1024 3 2048 0 ( m o d 4 ) 8^{2048}-6^{2048} \equiv 0-2^{2048} \cdot 3^{2048} \equiv -4^{1024} \cdot 3^{2048} \equiv 0 \pmod 4

8 2048 6 2048 1 2048 ( 1 ) 2048 1 1 0 ( m o d 7 ) 8^{2048}-6^{2048} \equiv 1^{2048}-(-1)^{2048} \equiv 1 - 1 \equiv 0 \pmod 7

8 2048 6 2048 2 6144 m o d ϕ ( 25 ) 6 2048 m o d ϕ ( 25 ) 2 6144 m o d 20 6 2048 m o d 20 ( m o d 25 ) 2 4 6 8 16 1 1 4 16 2 1 2 16 16 0 ( m o d 25 ) \begin{aligned} 8^{2048}-6^{2048} &\equiv 2^{6144 \mod \phi(25)}-6^{2048 \mod \phi(25)} \equiv 2^{6144 \mod 20}-6^{2048 \mod 20} \pmod{25}\\ &\equiv 2^4-6^8 \equiv 16-11^4 \equiv 16-21^2 \equiv 16 - 16 \equiv 0 \pmod {25} \end{aligned}

So, 8 2048 6 2048 0 ( m o d 700 ) 8^{2048}-6^{2048} \equiv 0 \pmod{700} , and we conclude that 8 2048 6 2048 8^{2048}-6^{2048} is divisible by 700 700 .

Nivedit Jain
Mar 12, 2017

Viki Zeta
Mar 10, 2017

8 2048 6 2048 = 2 3 × 2048 2 2048 × 3 2048 = 2 2048 [ 2 2 × 2048 3 2048 ] Now we eliminate all a n + b n as they won’t simply be said to divide 7. We’ll take and reduce all numbers of the form a n b n = 4 2048 3 2048 = ( 4 1024 + 3 1024 ) ( 4 1024 3 1024 ) 2048 = 2 × 1024 = 4 512 3 512 1024 = 2 × 512 = 4 256 3 256 512 = 2 × 256 = 4 128 3 128 256 = 2 × 128 = 4 64 3 64 128 = 2 × 64 = 4 32 3 32 64 = 2 × 32 = 4 16 3 16 32 = 2 × 16 = 4 8 3 8 16 = 2 × 8 = 4 4 3 4 8 = 2 × 4 = 4 2 3 2 4 = 2 × 2 ( 4 + 3 ) ( 4 3 ) 7 1 = 7 8^{2048} - 6^{2048} \\ = 2^{3 \times 2048} - 2^{2048} \times 3^{2048} \\ = 2^{2048} [ 2^{2 \times 2048} - 3^{2048} ] \\ \text{Now we eliminate all }a^n + b^n \text{ as they won't simply be said to divide 7. We'll take and reduce all numbers of the form } a^n - b^n = 4^{2048} - 3^{2048} \\ = (4^{1024} + 3^{1024})(4^{1024} - 3^{1024}) ~~ \boxed{2048 = 2 \times 1024}\\ = 4^{512} - 3^{512} ~~ \boxed{1024 = 2 \times 512}\\ = 4^{256} - 3^{256} ~~ \boxed{512 = 2 \times 256}\\ =4^{128} - 3^{128} ~~ \boxed{256 = 2 \times 128}\\ = 4^{64} - 3^{64} ~~ \boxed{128 = 2 \times 64}\\ = 4^{32} - 3^{32} ~~ \boxed{64 = 2 \times 32}\\ = 4^{16} - 3^{16} ~~ \boxed{32 = 2 \times 16}\\ = 4^{8} - 3^{8} ~~ \boxed{16 = 2 \times 8}\\ = 4^{4} - 3^{4} ~~ \boxed{8 = 2 \times 4}\\ = 4^{2} - 3^{2} ~~ \boxed{4 = 2 \times 2}\\ \boxed{\implies (4+3)(4-3) \implies 7 * 1 = 7}


Even simpler using congruency.

8 1 ( m o d 7 ) 8 2048 1 2048 1 ( m o d 7 ) 6 1 ( m o d 7 ) 6 2048 1 2048 1 ( m o d 7 ) 8 2048 6 2048 1 1 = 0 ( m o d 7 ) 7 ( 8 2048 6 2048 ) 8 \equiv 1 (\mathrm{mod} \ 7) \\ 8^{2048} \equiv 1^{2048} \equiv 1 (\mathrm{mod} \ 7) \\ 6 \equiv -1 (\mathrm{mod} \ 7) \\ 6^{2048} \equiv -1^{2048} \equiv 1 (\mathrm{mod} \ 7) \\ 8^{2048} - 6^{2048} \equiv 1 - 1 = 0 (\mathrm{mod} \ 7) \\ \boxed{\therefore 7 | (8^{2048} - 6^{2048})}

Can you show why it is divisible by 100 as well?

Freddie Hand - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...