For a positive integer n , let ϕ ( n ) denotes the Euler's totient function .
And let S k = n ∑ n ϕ ( n ) , where n runs through all positive divisors of 4 2 k . Find the largest positive integer k < 1 0 0 0 such that S k is an integer.
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.
how did you say that k=996 at the last step?
The function g ( n ) = d ∣ n ∑ n φ ( n ) is multiplicative , so g ( 4 2 k ) = g ( 2 k ) g ( 3 k ) g ( 7 k ) .
For any prime p and nonnegative integer k , direct computation shows that g ( p k ) = 1 + k ( 1 − 1 / p ) . So g ( 4 2 k ) = ( 1 + 2 k ) ( 1 + 3 2 k ) ( 1 + 7 6 k ) = 4 2 ( k + 2 ) ( 2 k + 3 ) ( 6 k + 7 ) . This is an integer if and only if the numerator is divisible by 2 , 3 , and 7 , which happens if and only if k k k ≡ 0 ( m o d 2 ) ≡ 0 , 1 ( m o d 3 ) ≡ 0 , 2 , 5 ( m o d 7 ) By the Chinese remainder theorem , this is equivalent to k ≡ 0 , 1 2 , 1 6 , 2 8 , 3 0 , 4 0 ( m o d 4 2 ) and since 1 0 0 0 ≡ 3 4 ( m o d 4 2 ) , the largest integer less than 1 0 0 0 that fits the requirements is 9 9 6 .
Problem Loading...
Note Loading...
Set Loading...
for a given k , n = 2 α 3 β 7 γ , for integer 0 ≤ α , β , γ ≤ k .
Then we can consider cases
1- 1 ≤ α , β , γ ≤ k
2 α 3 β 7 γ ϕ ( 2 α 3 β 7 γ ) = 7 2
there is gonna be k 3 such numbers n = 2 α 3 β 7 γ
2- exactly one of α , β , γ is zero. If α = 0
3 β 7 γ ϕ ( 3 β 7 γ ) = 7 4
there is gonna be k 2 such numbers n = 2 α 3 β 7 γ
similarly, if β = 0 or If γ = 0 , the fraction would be 7 3 and 3 1 , respectively. Each would contain k 2 numbers n .
3- exactly two of α , β , γ are zero. If α = 0
2 α ϕ ( 2 α ) = 2 1
there is gonna be k such numbers n = 2 α 3 β 7 γ
similarly, ff β = 0 or If γ = 0 , the fraction would be 3 2 and 7 6 , respectively. Again, each would contain k numbers n .
4- all three of α , β , γ are zero.
1 ϕ ( 1 ) = 1
there would be a single number n = 1 in this case.
So, we form the summation again
7 2 k 3 + 2 1 2 8 k 2 + 4 2 8 5 k + 1 = 4 2 1 2 k 3 + 5 6 k 2 + 8 5 k + 1
so we need to find the largest k < 1 0 0 0 ,for which 4 2 1 2 k 3 + 5 6 k 2 + 8 5 k is an integer. From this point, I ran a program to find the largest k , although an analytical approach seems to be easily achievable (rather cumbersome though). the largest would be k = 9 9 6