Giả sử $n=3k+r$, với $0\le r\le 2$.
Ta có:
$1^n+3^n+9^n=1^k.1^r+27^k.3^r+729^k.9^r\equiv 1^r+3^r+9^r\;($mod $13)$.
Đặt $S=1^r+3^r+9^r$.
Với $r=0$ thì $S=3\equiv 3\;($mod $13)$.
Với $r=1$ thì $S=13\equiv 0\;($mod $13)$.
Với $r=2$ thì $S=91\equiv 0\;($mod $13)$.
Suy ra: $1^n+3^n+9^n$ chia hết cho 13 khi $n$ không chia hết cho 3 và $1^n+3^n+9^n$ chia cho 13 dư 3 khi $n$ chia hết cho 3.