# Smallest positive integer a such that $5n^{13}+13n^5+a(9n)\equiv 0\pmod{65}$

How would you find the smallest positive integer $a$ such that $$5n^{13}+13n^5+a(9n)\equiv 0\pmod{65}$$ I simplified the polynomial in terms of $\bmod 5$ and $\bmod 13$ to get $3n+4na \equiv 0 \pmod{5}$ and $5n+9an \equiv 0 \pmod{13}$ but from here I'm stuck on how to proceed to solve for $a$.

• this means $$5n^{13}+13n^5+9an\equiv 0 \mod 65$$? – Dr. Sonnhard Graubner Dec 4 '17 at 18:45

Remember lil' Fermat can be written as $$\forall n,\:n^5\equiv n\mod5\qquad\text{ and }\qquad\forall n,\:n^{13}\equiv n\mod13.$$ So we have to solve the system of simultaneous congruences: $$\forall n,\begin{cases} 13n+9an\equiv 3n-an\equiv0\mod 5\\ 5n+9an\equiv 5n-4an\equiv0\mod 13 \end{cases}\iff \begin{cases} a\equiv \color{red}{3\mod 5},\\ 4a\equiv5\iff a\equiv -3\cdot5\equiv \color{blue}{-2\mod13}\end{cases}.$$ Now, a Bézout's relation between $5$ and $13$ is $\;2\cdot 13-5\cdot 5=1$, so solutions of the system of congruences is $$x\equiv\color{red}3\cdot2\cdot \color{blue}{13}-(\color{blue}{-2})5\cdot \color{red}{5} \equiv 63\mod65.$$ Thus the smallest positive integer $a$ satisfying the given congruence for all $n$ is $\color{green}{63}$.
• how did you get that $13n+9an \equiv 3n-an \equiv0\mod 5$ – Skrrrrrtttt Dec 4 '17 at 19:49
• Just because $13\equiv 3$ and $9\equiv -1\mod 5$. – Bernard Dec 4 '17 at 19:53
$65$ divides $$5(n^{13}-n)+13(n^5-n)$$ using Fermat's little theorem
• @Skrrrrrtttt , So, $65$ needs to divide $9(a+2)$ But as $(9,65)=1$ we need $$a+2\equiv0\pmod{65}\iff a\equiv-2\equiv-2+65$$ – lab bhattacharjee Dec 5 '17 at 0:26