I took a test in number theory and modular arithmetic today, and one of the questions looked like this:
Two grasshoppers A and B hop in a circle that is divided into 81 squares. The squares are numbered from 0 to 80. Grasshopper A starts on square no. 5 and hops 15 squares clockwise with each jump. Grasshopper B starts on square no. 80 and jumps 14 squares anticlockwise with each jump. They always jump at the same time. After how many jumps do they bump into each other for the first time? (i.e. when are they on the same square for the first time)
I tried doing it like this:
Let the clockwise direction be positive, and let $0\le p\le 81$ denote the position of a grasshopper after $n$ moves. Then, the position of A and B can be found using: $\displaystyle 15n+5\equiv_{81}p_A$ and $\displaystyle 80-14n\equiv_{81}p_B$, respectively. Now, since we want their position to be the same, we have to find the smallest integer solution to the following congruence: $\displaystyle 15n+5\equiv_{81}80-14n$ which is equivalent to $29n \equiv_{81} 75 \equiv_{81} -6$.
This is where I did not get any further. I have no idea how to find $n$ (and using systematic testing gave 0 points). Apparently, my professor suggested rewriting it as a diophantine equation but that doesn't exactly seem easier. Any suggestion on how to solve for $n$ is greatly appreciated!
$5+15n\equiv -1-14n \mod(81) \Rightarrow 6+29n\equiv 0\mod(81) \Rightarrow 29n\equiv -6 \mod(81)$.
The inverse of $29$ modulo $81$ is $14$, so we have $n\equiv -84 \equiv 78 \mod(81)$.
Check: if $n=78$, then $5+15\cdot78 = 1175\equiv 41 \mod(81)$. Likewise, $-1-14\cdot78 = -1093 \equiv 41 \mod(78)$.
In conclusion, it takes $78$ jumps for grasshoppers A and B to bump into each other for the first time.
As noted in the comments, the key step was to find the multiplicative inverse of $29$ modulo $81$. This number, call it $x$, is such that $29x\equiv 1\mod(81)$. It can be found a variety of ways, the two most common being the Euclidean algorithm (already noted in the comments) and trial multiplication by each number from $1$ to $80$. Of course, trial multiplication works best when dealing with small moduli and in fact is often quicker than the Euclidean algorithm in such a case.