余りに関する記述は合同式を用いるとよいでしょう．

与えられた条件はｎに含まれる素因数2はr個ある(0個も含む)ということです．
(1)与えられた2項係数が因数ｎをもてばこの中に2はr個あり，あと一つ別なところに2があれば，素因数2は合計r+1個となります．
(2)最大公約数が2の(r+1)乗であるということは，「公約数として2を(r+1)個含むが，(r+2)個含むことはない，かつ，2以外の公約数は存在しない」ということです．

2つの整数x，yとこの2数の最大公約数G，最小公倍数Lの間には「xy=GL」という関係が成り立ちます．