Proving Multiples in Exponents

1 7 7 17 \large 17^{7} - 17 Is the above number a multiple of 36?

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.

15 solutions

1 7 7 17 = 17 ( 1 7 6 1 ) = 17 ( ( 1 7 2 ) 3 1 ) = 17 ( 1 7 2 1 ) ( 1 7 4 + 1 7 2 + 1 ) 17^{7} - 17 = 17(17^{6} - 1) = 17((17^{2})^{3} - 1) = 17(17^{2} - 1)(17^{4} + 17^{2} + 1) ,

where the identity a 3 b 3 = ( a b ) ( a 2 + a b + b 2 ) a^{3} - b^{3} = (a - b)(a^{2} + ab + b^{2}) was used with a = 1 7 2 a = 17^{2} and b = 1 b = 1 .

Now 1 7 2 1 = ( 17 1 ) ( 17 + 1 ) = 16 × 18 = 8 × 36 17^{2} - 1 = (17 - 1)(17 + 1) = 16 \times 18 = 8 \times 36 . Thus the answer is Yes \boxed{\text{Yes}} .

Elegant, but missing a few steps. Thanks!

Donald Zacherl - 4 years ago
Chew-Seong Cheong
May 24, 2017

1 7 7 17 17 ( 18 1 ) 6 17 17 ( 1 ) 6 17 17 17 0 (mod 36) \begin{aligned} 17^7 - 17 & \equiv 17(18-1)^6 - 17 \equiv 17(-1)^6-17 \equiv 17-17 \equiv 0 \text{ (mod 36)} \end{aligned} . Yes , 1 7 7 17 17^7-17 is a multiple of 36.

I am not following one step. How did you get ( 18 1 ) 6 ( 1 ) 6 ( m o d 36 ) (18-1)^6 \equiv (-1)^6 \pmod {36} ? I got ( 18 1 ) 6 1 ( m o d 36 ) (18-1)^6 \equiv 1 \pmod {36} by using the binomial expansion.

Richard Costen - 4 years ago

Log in to reply

Yes ( 1 ) 6 = 1 (-1)^6 = 1 .

Chew-Seong Cheong - 4 years ago

by using formula expand (a+b)ⁿ

ning zhang - 4 years ago

I didn't understand this mod and all and how (18-1)^6=(-1)^6

DEEP PANDYA - 3 years, 10 months ago

Log in to reply

By binomial expansion: ( 18 1 ) 6 = 1 8 6 + 6 ( 18 ) 5 ( 1 ) + 15 ( 1 8 4 ) ( 1 ) 2 + 20 ( 1 8 3 ) ( 1 ) 3 + 15 ( 1 8 2 ) ( 1 ) 4 + 6 ( 18 ) ( 1 ) 5 + ( 1 ) 6 (18-1)^6 = 18^6+6(18)^5(-1)+15(18^4)(-1)^2+20(18^3)(-1)^3+15(18^2)(-1)^4+6(18)(-1)^5+(-1)^6 . Note that all the terms except the last one ( 1 ) 6 (-1)^6 are divisible by 36.

Chew-Seong Cheong - 3 years, 10 months ago
Pi Han Goh
May 24, 2017

Let λ ( ) \lambda(\cdot) denote the Carmichael's lambda function , then λ ( 36 ) = λ ( 2 2 3 2 ) = lcm ( λ ( 2 2 ) , λ ( 3 2 ) ) = lcm ( ϕ ( 2 2 ) , ϕ ( 3 2 ) ) = 6 , \lambda(36) = \lambda(2^2\cdot3^2) = \text{lcm}(\lambda(2^2), \lambda(3^2)) = \text{lcm}( \phi(2^2), \phi(3^2)) = 6 ,

where lcm \text{lcm} denotes the lowest common multiple function, and ϕ ( ) \phi(\cdot) denotes the Euler's totient function , with ϕ ( 2 2 ) = 2 2 ( 1 1 2 ) = 2 \phi(2^2) = 2^2 \left(1 - \dfrac12\right) = 2 and ϕ ( 3 2 ) = 3 2 ( 1 1 3 ) = 6 \phi(3^2) = 3^2 \left( 1 - \dfrac13\right) = 6 .

Knowing that a λ ( n ) 1 ( m o d n ) a^{\lambda(n)} \equiv 1 \pmod n for coprime positive integers a , n a,n , then

1 7 6 1 ( m o d 36 ) 1 7 7 17 ( m o d 36 ) \begin{aligned} 17^6 &\equiv &1 \pmod {36} \\ 17^7 &\equiv &17 \pmod {36} \\ \end{aligned}

Hence, 1 7 7 17 17^{7} - 17 is divisible by 36.

Interesting solution! I learnt something new today. :D

Tapas Mazumdar - 4 years ago

very nice problem.

Ramiel To-ong - 4 years ago

Didn't really need totient of 9 here. Simply 17^7 - 17 = (-1)^17 - (-1) = 0 (mod 9)

Jatin Sharma - 4 years ago

Log in to reply

Oh nevermind. I read it in a haste. Nice method. I checked divisibility by 4 and 9 separately.

Jatin Sharma - 4 years ago
Steven Yuan
May 27, 2017

Relevant wiki: Chinese Remainder Theorem

By the Chinese Remainder Theorem, if 1 7 7 17 17^7 - 17 is congruent to 0 modulo 9 and 4, then it is congruent to 0 modulo 36 as well, implying that 1 7 7 17 17^7 - 17 is a multiple of 36. Since

1 7 7 17 ( 1 ) 7 ( 1 ) 0 ( m o d 9 ) 17^7 - 17 \equiv (-1)^7 - (-1) \equiv 0 \! \! \! \! \pmod{9}

and

1 7 7 17 1 7 1 0 ( m o d 4 ) , 17^7 - 17 \equiv 1^7 - 1 \equiv 0 \! \! \! \! \pmod{4},

we conclude that 1 7 7 17 0 ( m o d 36 ) 17^7 - 17 \equiv 0 \pmod{36} , and Yes \boxed{\text{Yes}} , it is a multiple of 36.

Alex Li
May 28, 2017

1 7 0 = 1 m o d 36 17^0 = 1 \mod 36
1 7 1 = 17 m o d 36 17^1 = 17 \mod 36
1 7 2 = 1 m o d 36 17^2 = 1 \mod 36

Because numbers raised to higher powers always follow cyclical patterns mod N, we know that the next terms of 17^n will be 17,1,17,1,17. Therefore, 1 7 7 = 17 m o d 36 17^7 = 17 \mod 36 .

17 17 = 0 17- 17 = 0

Really nice simple solution. Neat. 😀

Justin Roughley - 4 years ago

Its very simple! :D

Gergely Stomfai - 3 years, 12 months ago
Diego Castaño
May 30, 2017

First mod 4:

1 7 7 17 1 7 1 = 0 ( m o d 4 ) 17^7-17 \equiv 1^7 - 1 = 0 \pmod{4} .

Then mod 9:

1 7 7 17 ( 1 ) 7 + 1 = 0 ( m o d 9 ) 17^7-17 \equiv (-1)^7+1 = 0 \pmod{9} .

Thus 4 and 9 both divide 1 7 7 17 17^7-17 , hence (since they are relatively prime) 36 = 4*9 also divides it.

Playing devil's advocate here.

Why must they be coprime in the first place? (17^7 - 17) is divisible by 18, and is divisible by 2 as well, so they are divisible by (18x2=36) as well. But 18 and 2 are not coprime. So what's the importance of them being coprime first?

Pi Han Goh - 4 years ago

Log in to reply

I am not sure what you're talking about. I used the following elementary property: if a and b divide c and gcd(a,b) = 1, then ab divides c. It is not valid if gcd(a,b) is not 1. For example: 18 is divisible both by 18 and 2, but 18 is not divisible by 36.

Diego Castaño - 3 years, 10 months ago

Log in to reply

Ah my bad, for some reason, I thought 4 and 9 are not coprime.

Pi Han Goh - 3 years, 10 months ago

Correct answer is: YES.

Carlos Marques
Jun 4, 2017

1 7 7 17 = 17 ( 1 7 6 1 ) = 17 ( 1 7 3 + 1 ) ( 1 7 3 1 ) 17^{7} -17=17(17^{6}-1)=17(17^{3}+1)(17^{3}-1)

Since 1 7 3 17^{3} is odd, both 1 7 3 1 17^{3}-1 and 1 7 3 + 1 17^{3}+1 are even.

Now:

1 7 3 + 1 = ( 18 1 ) 3 + 1 17^{3}+1=(18-1)^{3}+1

All the terms on the cubic expansion are multiples of 18 except for the last one ( 1 ) 3 = 1 (-1)^{3}=-1 which cancels with the +1 (in fact:

( 18 1 ) 3 = 1 8 3 3.1 8 2 + 3.18 1 (18-1)^{3}=18^{3}-3.18^{2}+3.18-1 )

So as one of the terms is multiple of 18 and the other is even, the product is multiple of 36.

Bonus

For two consecutive even numbers one is multiple of 4, so the result must bem multiple of 72

Bonus 2

( 18 1 ) 3 + 1 = 1 8 3 3.1 8 2 + 3 18 1 + 1 = 18 ( 1 8 2 3.18 + 3 ) (18-1)^{3}+1=18^{3}-3.18^{2}+3^{18}-1+1=18(18^{2}-3.18+3)

So this term must be a multiple of 18 × 3 18 \times 3 , and the result mus have another factor of 3, making the number multiple of 72 × 3 = 216 72 \times 3=216

Tom Verhoeff
Jun 4, 2017

n = 1 7 7 17 = 17 ( 1 7 6 1 ) = 17 ( 1 7 3 1 ) ( 1 7 3 + 1 ) n=17^7-17=17(17^6-1)=17(17^3-1)(17^3+1) . Both 1 7 3 1 17^3-1 and 1 7 3 + 1 17^3+1 are even; hence, n n is divisible by 4 4 . Since 17 17 is not divisible by 3 3 , exactly one of these factors is divisible by 3 3 . But that is not enough.

Consider 1 7 3 m o d 9 = ( 1 ) 3 m o d 9 = 1 17^3\bmod 9=(-1)^3\bmod 9=-1 . Hence, 1 7 3 + 1 17^3+1 is divisible by 9 9 . Therefore, n n is divisible by 4 × 9 = 36 4\times 9=36 .

Since 36 = 4 \cdot 9, if the expression is divisible by both 4 and 9, we are done. First we take mod 4:

17^7 - 7 \equiv (1)^7 - 1 \equiv 0 \pmod{4}

Next, mod 9:

17^7 - 7 \equiv (-1)^7 - (-1) \equiv 0 \pmod{9}

Thus the answer is YES .

Arjen Vreugdenhil
May 29, 2017

Evaluate modulo 4: 1 7 7 17 1 7 1 1 1 0 mod 4 . 17^7 - 17 \equiv 1^7 - 1 \equiv 1 - 1 \equiv 0 \ \ \text{mod 4}. Evaluate modulo 9: 1 7 7 17 ( 1 ) 7 ( 1 ) ( 1 ) ( 1 ) 0 mod 9 . 17^7 - 17 \equiv (-1)^7 - (-1) \equiv (-1) - (-1) \equiv 0 \ \ \text{mod 9}. It follows that 1 7 7 17 17^7 - 17 is a multiple both of 4 and 9, and therefore of their least common multiple, 36.

Eugene Alterman
May 29, 2017

17 1 ( m o d 4 ) 1 7 6 1 ( m o d 4 ) 4 ( 1 7 6 1 ) 17 1 ( m o d 9 ) 1 7 6 1 ( m o d 9 ) 9 ( 1 7 6 1 ) } 36 ( 1 7 6 1 ) 36 ( 1 7 7 17 ) \left . \begin{aligned} 17 \equiv 1 \pmod {4} \implies\ 17^6 \equiv 1 \pmod {4} \implies 4 \mid (17^6 - 1) \\ 17 \equiv -1 \pmod {9} \implies\ 17^6 \equiv 1 \pmod {9} \implies 9 \mid (17^6 - 1) \end {aligned} \right \} \implies 36 \mid (17^6 - 1) \implies 36 \mid (17^7 - 17)

Gandoff Tan
Jul 18, 2019

17 7 17 = 17 ( 17 6 1 ) = 17 ( 17 3 1 ) ( 17 3 + 1 ) = 17 ( 17 1 ) ( 17 2 + 17 + 1 ) ( 17 + 1 ) ( 17 2 17 + 1 ) = 17 ( 16 ) ( 18 ) ( 17 4 + 17 2 + 1 ) 17 7 17 = [ 17 ( 8 ) ( 17 4 + 17 2 + 1 ) ] ( 36 ) \begin{aligned} { 17 }^{ 7 }-17 & = 17\left( { 17 }^{ 6 }-1 \right) \\ \quad & = 17\left( { 17 }^{ 3 }-1 \right) \left( { 17 }^{ 3 }+1 \right) \\ \quad & = 17\left( 17-1 \right) \left( { 17 }^{ 2 }+17+1 \right) \left( 17+1 \right) \left( { 17 }^{ 2 }-17+1 \right) \\ \quad & = 17\left( 16 \right) \left( 18 \right) \left( { 17 }^{ 4 }+{ 17 }^{ 2 }+1 \right) \\ { 17 }^{ 7 }-17 & = \left[ 17\left( 8 \right) \left( { 17 }^{ 4 }+{ 17 }^{ 2 }+1 \right) \right] \left( 36 \right) \end{aligned}

Gordon Flygare
May 31, 2017

By testmanship, yes is the likely answer as it would make no sense to ask if the answer was no.

Why it make no sense to ask this question if the answer was no?

Pi Han Goh - 4 years ago

Log in to reply

Pi has a very good point. I posted this problem, although it has a simple solution, it was an elegant one. I hoped some people would post proofs, which they did. Math is something where you prove your answer. Otherwise, we can say that every single question asked is true or else what's the point.

Hasan Kunukcu - 2 years, 11 months ago
Bob Liddington
May 29, 2017

Without using algebra higher other than “the difference of 2 squares or cubes”, in general the statement holds true for X^Y - X when X is odd and Y is odd. (Apologies for using ^ for "raising to the power"; I haven't figured out formatting yet).

e.g. For X is odd and Y = 3, Substitute N=X+1, and the expression must be divisible by 2N.

Rearranging and taking the difference of squares:

(N-1)^3 - (N-1) = (N-1) [(N-1)^2 - 1] = (N-1) x [(N-2) x N]

Since N is even (and X is odd) then (N-2) is also even (and so divisible by 2), so the product [(N-2) x N]) is divisible by 2N.
QED.

For Y = 5, we get

(N-1)^5 - (N-1) = N-1 x [(N-1)^4 x [(N-1^2 -1], where [(N-1)^2 - 1)], is the only relevant factor, the same as that above.

Any odd value of Y can be factored this way, where only the factor [(N-2)xN] is relevant:

(N-1)^Y - (N-1) = (N-1) x [N-1]^(Y-1) x [(N-2) x N)]

However, whenever Y is even, e.g. 4, we have to take the difference of 2 cubes

(N-1)^4 - (N-1) = (N-1) x [(N-1)^3 - 1] = (N-1) x [(N-1)^2 - (N-1) + 1)] =

(N-1) x [(N-1)^2 - N)] which is not In general divisible by 2N (Seems obvious but I realize I have not provided a formal proof here)

You're close to proving a famous classical theorem. Keep working at it!

Pi Han Goh - 4 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...