New nice Problem 1

[rsoldo]

Prove that $3^{105}+4^{105}$ is divisible by 13, 49, 181 and 379, but isn't divisible by 5 and 11.

[scwec]

Maple

> 3^105+4^105=1645504557321331278892507061310792365037268911602846475476455267;
> ifactor(1645504557321331278892507061310792365037268911602846475476455267);
   2                                                              
(7)  (13) (31) (43) (181) (211) (379) (421) (631) (673) (5786971)  (35144971) (101855671) (3270961) (2131) (633151) (8191)

[nnosipov]

Не вижу смысла в этой задаче как олимпиадной: можно (даже вручную) вычислить степени по модулю с помощью бинарного алгоритма. Скучно. It's boring.

[rsoldo]

$105=3\cdot 5\cdot7$

First case:
$3^3\equiv 1\pmod{13}\implies 3^{105}\equiv 1^{35}\pmod{13}\implies 3^{105}\equiv 1\pmod{13}$
$4^3\equiv -1\pmod{13}\implies 4^{105}\equiv (-1)^{35}\pmod{13}\implies 4^{105}\equiv -1\pmod{13}$
$\implies 3^{105}+4^{105}\equiv 0\pmod{13}$

[Dendr]

One doesn't even need Fermat for the case of 49:
$3^{105}+4^{105}=3^{105}+(7-3)^{105}= \\3^{105}+7^{105}-105\cdot7^{104}\cdot3+...-\frac{105\cdot104}{2}7^2\cdot3^{103}+105\cdot7\cdot3^{104}-3^{105}$
After cancelling $3^{105}$'s it is obvious that this expression is divisible by 49.