Suppose that a is an integer such that $a^3=15k + 13$, where k is an Integer. What is the remainder when a is divided by 5? So this is a problem that I was given to solve in my modern algebra class. At first, I tried seeing if I could take the cube root of 15 but that obviously isn't a perfect cube. Next, I asked for help on Chegg, but the answer included content (modular arithmetic) that we haven't covered yet so I'm trying to figure out how to do this problem when we've only covered the division algorithm and divisors.
Any help would be greatly appreciated!
 A: may be you have gone through the group $\mathbb Z_n$ and $U(n)$. Then $U(4)$ will be a cyclic group of order 4. Now that is a hint you can work on.
And the ans will come out to be 2
A: Hint $5|a^3+2$. If you write $a=5m+r$ where the remainder is $r=0,1,2,3,4$, and plug in into the above equation, after opening the bracket in $(5m+r)^3$ you will discover that $5|r^3+2$. Since you only have 5 possibilities for $r$, you can check them all.
A: Note that :$$a^{4k+r}\equiv a^r \space (mod \space  10 ) \space r\in \{1,2,3,4\}  $$so
$$a^{4k+r}\equiv a^r \space (mod \space 5 ) \space r\in \{1,2,3,4\} \\\to  
a^5 \equiv a^9  \equiv a^{13} ...\equiv a^1$$ now 
$$a^3=15k+13 \to 
a^3\equiv 13 \equiv 3\space (mod \space 5 ) \space \\
(a^3\equiv 3)^3 \space (mod \space 5 ) \\
a^9\equiv 27 \space (mod \space 5 )\\
a^9\equiv 27-25 \space (mod \space 5 )\\
a^9\equiv a^1\equiv 2 \space (mod \space 5 )\\
a=5q+2$$
A: $\!\bmod 15\!:\ a^3\equiv 13\,\Rightarrow\, \bmod 5\!:\ \overbrace{ \color{#c00}{a^3}\equiv 3\,\Rightarrow\, a\equiv 1/3}^{\Large \color{#c00}{a^3\ \equiv\  a^{-1}}\  {\rm by}\ \  \color{#0a0}{a^4\ \equiv\ 1}}\equiv 6/3\equiv 2\ $ by little $\rm\color{#0a0}{Fermat}$
Remark $ $ The first $(\Rightarrow)$ uses the uniquitous fact that congruences persist modulo divisors of the modulus, since $\,a\equiv b\pmod{\!nk}\,\Rightarrow\, n\mid nk\mid a-b\,\Rightarrow\, n\mid a-b\,\Rightarrow\, a\equiv b\pmod{\! n}$ 
A: You said without modular arithmetic. Let's see.
Method 1: Add $2$ to both sides:
$$a^3+2=15k+15=15(k+1).$$
It implies $a^3+2$ must be divisible by $15$ or by $3$ and $5$. Divisibility by $5$ implies that $a^3+2$ must end with $5$ or $0$. Then it implies that $a^3$ must end with $3$ or $8$. For $a^3$ to end with $3$ or $8$, $a$ must end with either $2$ or $7$. Then when $a$ is divided by $5$ gives the remainder $2$.
Method 2: Note that $15k+13$ ends either with $3$ or $8$. (For example, when $k$ is even, ends with $3$, when $k$ is odd, it ends with $8$). It means $a^3$ must also end with either $3$ or $8$. It means $a$ must end with either $7$ or $2$. It means $a$ divided by $5$ gives the remainder $2$.
