じゃあこうだ。
3で割って1余る任意の整数は、適切な整数mによって3m+1の形で一意に表せる。
また、この整数mは別の適切な整数nと0≦a≦3の範囲の整数aによって、
m=4n+aの形で一意に表せる。
このとき、3m+1=3*(4n+a)+1=12n+(3a+1)=4*3ｎ+(3a+1)であるから、
この整数3m+1を4でわって割り切れるとき、3a+1が4の倍数でなければならない。
したがって0≦a≦3であるから、a=1でなければならない。
このとき、3m+1=3*(4n+1)+1=12ｎ+4であり、これを12で割れば余りは4である。

エレガントでも簡潔でもないが。