IZhO олимпиада по математике 2020 года | Казахстанские олимпиады

Натуральное число $n$ таково, что ни при каких натуральных $a$ и $b$ число $2^a3^b+1$ не делится на $n$. Докажите, что $2^c+3^d$ также не делится на $n$ ни при каких натуральных $c$ и $d$.