Spring 2016, problem 13
Comments
The browser interprets the < as the start of an html tag or something like that. Use \lt and \leq inside $ signs instead.
The number n has the required property, if and only if n=2k for some positive integer k.
I suspect, there's a nice proof for that, involving the binomial theorem and a little group theory, but all I could come up was this rather calculational Proof:
[The notation ⌊x⌋:=floor(x) and ⌈x⌉:=ceil(x) is used throughout.]
For every natural a, define ν(a):=b, where b is the largest integer, such that 2b divides a. Or put another way: ν(a) is the numbert of twos in the prime factorization of a.
A particular case of a result known as Legendre's formula states, that for all a∈N:
ν(a!)=∑∞i=1⌊a2i⌋
Also, from the definition of the binomial coefficients, we have:
ν((nk))=ν(n!)−ν(k!)−ν([n−k]!) (*)
Now assume, that n is not a power of 2. So n lies strictly between two powers 2j and 2j+1 of two, i.e. there are j,r∈N, with 0<r<2j, such that n=2j+r.
Then ν(n!)=ν([2j+r]!)=∑∞i=1⌊2j+r2i⌋=∑ji=12j−i+⌊r2i⌋=ν([2j]!)+ν(r!). Note, that the second manipulation only works, because we assume, that r<2j. Plugging this into the equation (*), we get:
ν((n2j))=ν((2j+r2j))=ν([2j]!)+ν(r!)−ν([2j]!)−ν(r!)=0
Therefore (n2j) is odd so that n does not have the property required in the problem statement.
This concludes the first half of the proof. We now assume, that n=2j for some j∈N and prove it does indeed have said property.
Pick a k∈N, such that 0<k<2j. Then:
ν((nk))=ν((2jk))=ν([2j]!)−ν([2j−k]!)−ν(k!)=∑ji=1⌈k2i⌉−⌊k2i⌋. By the definition of the rounding functions, none of the summands is negative and - from 0<k<2j - the last one is equal to 1. Therefore ν((nk))>=1 and so (nk) is even. This completes the proof.
As an aside, using the general form of Legendre's formula, the proof takes little modification, to show that:
A prime number p divides all of (n1),(n2),…,(nn−1) iff n is a power of p.
Hi, I'm Hubert from Paris ... Luca's theorem shows that n=2q;
using the Wikipedia article notations with p=2 we want N=(mn) even for 1≤n≤m−1,
if m is not a power of 2, then mk=mj=1 for some j<k and the given formula says (m2j)≡(11)(mod2) with nj=1,nk=0,k≠j, odd;
now if m=2k,mj=0,j<k and n<m⇒ nk=0, and at least one of the n0,n1,⋯nk−1 is one, putting a 0=(01) in the given product, for each n∈(0,m), making each N even.
Note: this strange < is the symbol "less than", can someone fix that ?
I need your help now ... :-(