How Many Integers Make This Square Free?
Let S be the sum of all positive integers N for which the number N N − 1 − 1 isn't divisible by any perfect squares apart from 1 . Find S + 1 .
The answer is 3.
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.
4 solutions
Sketch:For all N it is divisible by ( N − 1 ) 2 (use N ≡ 1 ( m o d N − 1 ) )That leaves 1 and 2.
Alternatively, for any prime p dividing N − 1 , v p ( N N − 1 − 1 ) = v p ( N − 1 ) + v p ( N − 1 ) ≥ 2 by LTE.
Nice solution! But for N = 1 , N N − 1 − 1 = 0 , which is divisible by any positive integer. So the answer is 2.
Log in to reply
Yes, I noticed that and think the answer should be changed.
Yes, I noticed my mistake and have edited the question accordingly.
Note that for all N > 0 the expression is divisible by ( N − 1 ) 2 .
Write the number in base N . Factor N N − 1 − 1 into ( N − 1 ) ( N N − 2 + N N − 3 + ⋯ + 1 ) . Clearly, N − 1 ∣ N − 1 .
If the sum of the digits of a number in base k is divisible by k − 1 , it is divisible by k − 1 . In base N , N N − 2 + N N − 3 + ⋯ + 1 consists of N − 1 1s, which sums to N − 1 . Therefore, all numbers of this form have 2 factors of N − 1 . Therefore N − 1 = 1 , so N = 2 . Thus, S = 2 + 1 = 3 .
May I ask the motivation of asking for S+1 and not S?
When I published this problem, I entered an incorrect answer ( 2 ). Now may I ask the "motivation" for posting this as a solution instead of a comment?
Shift N → N + 1 to get ( N + 1 ) N − 1 . Now we have for all N ≥ 1 ( N + 1 ) N − 1 = k = 0 ∑ N ( k N ) N k − 1 = k = 1 ∑ N ( k N ) N k ≡ ( 1 N ) N = N 2 ≡ 0 ( m o d N 2 ) Note that N = 1 is a valid case since divisibility by 1 2 is allowed. This gives N = 2 a solution. N = 0 gives ( N + 1 ) N − 1 = 0 which is divisible by every single perfect square in the world so the answer should be 2 . When it didn't work I considered 1 as a solution and put 3 , it worked.