1 7 7 − 1 7 Is the above number a multiple of 36?
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.
Elegant, but missing a few steps. Thanks!
1 7 7 − 1 7 ≡ 1 7 ( 1 8 − 1 ) 6 − 1 7 ≡ 1 7 ( − 1 ) 6 − 1 7 ≡ 1 7 − 1 7 ≡ 0 (mod 36) . Yes , 1 7 7 − 1 7 is a multiple of 36.
I am not following one step. How did you get ( 1 8 − 1 ) 6 ≡ ( − 1 ) 6 ( m o d 3 6 ) ? I got ( 1 8 − 1 ) 6 ≡ 1 ( m o d 3 6 ) by using the binomial expansion.
Log in to reply
Yes ( − 1 ) 6 = 1 .
by using formula expand (a+b)ⁿ
I didn't understand this mod and all and how (18-1)^6=(-1)^6
Log in to reply
By binomial expansion: ( 1 8 − 1 ) 6 = 1 8 6 + 6 ( 1 8 ) 5 ( − 1 ) + 1 5 ( 1 8 4 ) ( − 1 ) 2 + 2 0 ( 1 8 3 ) ( − 1 ) 3 + 1 5 ( 1 8 2 ) ( − 1 ) 4 + 6 ( 1 8 ) ( − 1 ) 5 + ( − 1 ) 6 . Note that all the terms except the last one ( − 1 ) 6 are divisible by 36.
Let λ ( ⋅ ) denote the Carmichael's lambda function , then λ ( 3 6 ) = λ ( 2 2 ⋅ 3 2 ) = lcm ( λ ( 2 2 ) , λ ( 3 2 ) ) = lcm ( ϕ ( 2 2 ) , ϕ ( 3 2 ) ) = 6 ,
where lcm denotes the lowest common multiple function, and ϕ ( ⋅ ) denotes the Euler's totient function , with ϕ ( 2 2 ) = 2 2 ( 1 − 2 1 ) = 2 and ϕ ( 3 2 ) = 3 2 ( 1 − 3 1 ) = 6 .
Knowing that a λ ( n ) ≡ 1 ( m o d n ) for coprime positive integers a , n , then
1 7 6 1 7 7 ≡ ≡ 1 ( m o d 3 6 ) 1 7 ( m o d 3 6 )
Hence, 1 7 7 − 1 7 is divisible by 36.
Interesting solution! I learnt something new today. :D
very nice problem.
Didn't really need totient of 9 here. Simply 17^7 - 17 = (-1)^17 - (-1) = 0 (mod 9)
Log in to reply
Oh nevermind. I read it in a haste. Nice method. I checked divisibility by 4 and 9 separately.
Relevant wiki: Chinese Remainder Theorem
By the Chinese Remainder Theorem, if 1 7 7 − 1 7 is congruent to 0 modulo 9 and 4, then it is congruent to 0 modulo 36 as well, implying that 1 7 7 − 1 7 is a multiple of 36. Since
1 7 7 − 1 7 ≡ ( − 1 ) 7 − ( − 1 ) ≡ 0 ( m o d 9 )
and
1 7 7 − 1 7 ≡ 1 7 − 1 ≡ 0 ( m o d 4 ) ,
we conclude that 1 7 7 − 1 7 ≡ 0 ( m o d 3 6 ) , and Yes , it is a multiple of 36.
1
7
0
=
1
m
o
d
3
6
1
7
1
=
1
7
m
o
d
3
6
1
7
2
=
1
m
o
d
3
6
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 = 1 7 m o d 3 6 .
1 7 − 1 7 = 0
Really nice simple solution. Neat. 😀
Its very simple! :D
First mod 4:
1 7 7 − 1 7 ≡ 1 7 − 1 = 0 ( m o d 4 ) .
Then mod 9:
1 7 7 − 1 7 ≡ ( − 1 ) 7 + 1 = 0 ( m o d 9 ) .
Thus 4 and 9 both divide 1 7 7 − 1 7 , 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?
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.
Log in to reply
Ah my bad, for some reason, I thought 4 and 9 are not coprime.
Correct answer is: YES.
1 7 7 − 1 7 = 1 7 ( 1 7 6 − 1 ) = 1 7 ( 1 7 3 + 1 ) ( 1 7 3 − 1 )
Since 1 7 3 is odd, both 1 7 3 − 1 and 1 7 3 + 1 are even.
Now:
1 7 3 + 1 = ( 1 8 − 1 ) 3 + 1
All the terms on the cubic expansion are multiples of 18 except for the last one ( − 1 ) 3 = − 1 which cancels with the +1 (in fact:
( 1 8 − 1 ) 3 = 1 8 3 − 3 . 1 8 2 + 3 . 1 8 − 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
( 1 8 − 1 ) 3 + 1 = 1 8 3 − 3 . 1 8 2 + 3 1 8 − 1 + 1 = 1 8 ( 1 8 2 − 3 . 1 8 + 3 )
So this term must be a multiple of 1 8 × 3 , and the result mus have another factor of 3, making the number multiple of 7 2 × 3 = 2 1 6
n = 1 7 7 − 1 7 = 1 7 ( 1 7 6 − 1 ) = 1 7 ( 1 7 3 − 1 ) ( 1 7 3 + 1 ) . Both 1 7 3 − 1 and 1 7 3 + 1 are even; hence, n is divisible by 4 . Since 1 7 is not divisible by 3 , exactly one of these factors is divisible by 3 . But that is not enough.
Consider 1 7 3 m o d 9 = ( − 1 ) 3 m o d 9 = − 1 . Hence, 1 7 3 + 1 is divisible by 9 . Therefore, n is divisible by 4 × 9 = 3 6 .
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 .
Evaluate modulo 4: 1 7 7 − 1 7 ≡ 1 7 − 1 ≡ 1 − 1 ≡ 0 mod 4 . Evaluate modulo 9: 1 7 7 − 1 7 ≡ ( − 1 ) 7 − ( − 1 ) ≡ ( − 1 ) − ( − 1 ) ≡ 0 mod 9 . It follows that 1 7 7 − 1 7 is a multiple both of 4 and 9, and therefore of their least common multiple, 36.
1 7 ≡ 1 ( m o d 4 ) ⟹ 1 7 6 ≡ 1 ( m o d 4 ) ⟹ 4 ∣ ( 1 7 6 − 1 ) 1 7 ≡ − 1 ( m o d 9 ) ⟹ 1 7 6 ≡ 1 ( m o d 9 ) ⟹ 9 ∣ ( 1 7 6 − 1 ) } ⟹ 3 6 ∣ ( 1 7 6 − 1 ) ⟹ 3 6 ∣ ( 1 7 7 − 1 7 )
1 7 7 − 1 7 1 7 7 − 1 7 = 1 7 ( 1 7 6 − 1 ) = 1 7 ( 1 7 3 − 1 ) ( 1 7 3 + 1 ) = 1 7 ( 1 7 − 1 ) ( 1 7 2 + 1 7 + 1 ) ( 1 7 + 1 ) ( 1 7 2 − 1 7 + 1 ) = 1 7 ( 1 6 ) ( 1 8 ) ( 1 7 4 + 1 7 2 + 1 ) = [ 1 7 ( 8 ) ( 1 7 4 + 1 7 2 + 1 ) ] ( 3 6 )
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?
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.
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!
Problem Loading...
Note Loading...
Set Loading...
1 7 7 − 1 7 = 1 7 ( 1 7 6 − 1 ) = 1 7 ( ( 1 7 2 ) 3 − 1 ) = 1 7 ( 1 7 2 − 1 ) ( 1 7 4 + 1 7 2 + 1 ) ,
where the identity a 3 − b 3 = ( a − b ) ( a 2 + a b + b 2 ) was used with a = 1 7 2 and b = 1 .
Now 1 7 2 − 1 = ( 1 7 − 1 ) ( 1 7 + 1 ) = 1 6 × 1 8 = 8 × 3 6 . Thus the answer is Yes .