MathLabs

Problem 3

For any positive integer n n , let d(n) d(n) denote the number of positive divisors of n n (including 11 and n n itself). Determine all positive integers k k such that d(n2)d(n)=k\frac{d(n^2)}{d(n)}=k for some n n .
Step 4 of 6: Induct on an odd integer
Previous stepNext step
In plain words

Extract a smaller odd integer y y .

k+1=2ty,y odd,x=k−yk+1=2^t y,\quad y\text{ odd},\quad x=k-y
Detailed analysis

For odd k>1 k>1, write k+1=2ty k+1=2^t y with y y odd. Then 1≤y<k1\le y<k and k+1=2t(k−x) k+1=2^t(k-x) where x=k−y x=k-y . Rearranging gives k/y=(2tx+1)/(x+1) k/y=(2^t x+1)/(x+1).