Chinese remainder theorem ?
Note that if the remainder in the division by 4 is 1, then it is 1 in the division by 2 too. Because K=4k+1=2*(2k)+1. So you don't need to bother yourself working on 2.
Same goes for K=6k'+1=3*(2k)+1
Edit : never say you're an idiot.