If n is an integer greater than 7 then ( 7 n ) − ⌊ 7 n ⌋ is divisible by:
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.
Original solution:::::
We have ( 7 n ) = 7 ! n ( n − 1 ) ( n − 2 ) ⋯ ( n − 6 ) .
In the numerator, there is a factor divisible by 7, and the other six factors leave the remainders 1, 2, 3, 4, 5, 6, in some order when divided by 7.
Hence the numerator may be written as
7 k ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ⋯ ( 7 k 6 + 6 )
Also we conclude that [ p n ] = k , as in the set { n , n − 1 , … , n − 6 } , 7 k is the only number which is a multiple of 7. If the given number is called Q , then
Q = = = 7 k 7 ! ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ⋯ ( 7 k 6 + 6 ) − k k ⋅ 6 ! ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ⋯ ( 7 k 6 + 6 ) − 6 ! 6 ! 7 t k
We know that Q is an integer, and so 6 ! divides 7 t k . Since g cd ( 7 , 6 ! ) = 1 , even after cancellation there is a factor of 7 still left in the numerator. Hence 7 divides Q , as desired.
Just kidding, got it from Solutions to CRMO-2003 .
Log in to reply
Whoa! Nice work! +1
Log in to reply
I know. I thought of it myself.
@Ameya Salankar , is this the intended proof? I'm not sure whether we're allowed to use such heavy machinery like Lucas' Theorem for RMO problems. Is there, perhaps, a more elementary solution to this (other than my approach) ?
If there is, I'm guessing it's quite possibly an inductive proof?
Log in to reply
elemetary hint - 7 is a prime number
Log in to reply
If you observe, I also used the fact that 7 is a prime number in my solution.
Does anyone have an elementary solution ? I am unable to find one.
There might be. Try searching for one in the official website of RMO.
Problem Loading...
Note Loading...
Set Loading...
Since n ∈ Z > 7 , its base 7 representation contains more than or equal to 2 digits. More precisely, consider the base 7 representation of n as follows:
where q is some non-negative integer ≥ 1 depending on the value of n satisfying the inequality (bounding) stated above.
Also, it's obvious by definition of base 7 expansion that all the n i 's are non-negative integers depending on the value of n which satisfy 0 ≤ n i ≤ 6 (this idea is used while evaluating the floor expression).
Also, we have 7 1 0 = 1 0 7 = ( q − 1 ) digits 0 0 0 ⋯ 1 0 7 .
Proof: We use Lucas' Theorem noting the fact that 7 is a prime.
( 7 n ) ≡ ( 0 n 0 ) ⋅ ( 1 n 1 ) ⋅ k = 2 ∏ q ( 0 n k ) ≡ 1 ⋅ n 1 ⋅ k = 2 ∏ q 1 ≡ n 1 ( m o d 7 )
Then again, using the base 7 expansion of n , we easily have,
⌊ 7 n ⌋ = ⌊ ( k = 2 ∑ q n k 7 k − 1 ) + n 1 + 7 n 0 ⌋ = ( k = 2 ∑ q n k 7 k − 1 ) + n 1 + ⌊ 7 n 0 ⌋ ⟹ ⌊ 7 n ⌋ = ( k = 2 ∑ q n k 7 k − 1 ) + n 1 + 0 ≡ 0 + n 1 + 0 ≡ n 1 ( m o d 7 )
Hence, we conclude that ∀ n ∈ Z > 7 , we have,
( 7 n ) − ⌊ 7 n ⌋ ≡ n 1 − n 1 ≡ 0 ( m o d 7 ) ⟺ 7 ∣ ( 7 n ) − ⌊ 7 n ⌋
For disproving the other options, it's easy to show a counter-example like n = 8 which ∈ Z > 7 easily disproves all the other three options.