En el fondo ambos razonamientos están basados en el siguiente hecho:
Si k divide a x y k divide a z, entonces k divide a x-z
Esto, creo que no requiere demostración (la requiere, pero es obvia)
Ahora, con respecto a mi primer argumento:
Si k divide a 2n y k divide a 2n+1, debe dividir a 2n+1-2n=1 es decir que k=1.
El segundo argumento da una vuelta inicial por que está claroque si k divide a n+3 también dividirá a cualquier mútiplo suyo; en particular, a 2n+6. Si suponemos pues que además k divide a 2n+1 otra vezaplicando el resultado anterior tenemos que k debe dividir a 2n+6-2n-1=5, es decir, que k=1 ó 5.
Espero haber sido algo más claro.
Saludos.