Modular Inverses Question

What is the smallest positive integer $a$ such that $a^{-1}$ is undefined $\pmod{55}$ and $a^{-1}$ is also undefined $\pmod{66}$?

How do I solve this problem? Modular inverses is new to me.

HINT: An inverse of $a$ modulo $n$ exists iff $a$ and $n$ are relatively prime.

One way to prove this hint is to make use of Bézout's Identity connected directly to the Extended Euclidean Algorithm stating that there exist $x,y\in\mathbb Z$ such that: $$ax+ny=\gcd(a,n)$$ an then note that for any $x',y'\in\mathbb Z$ we know that $\gcd(a,n)$ almost by definition divides the expression: $$ax'+ny'$$ since it divides $a$ and $n$. Thus the equation $$ax'+ny'=1$$ has a solution if and only if $\gcd(a,n)=1$, which in turn is equivalent to showing the existence of the inverse $a^{-1}=x'$.

• Why isn't the answer 11, then? – Dreamer Aug 31 '16 at 20:09
• @Regina: Indeed it is! – String Aug 31 '16 at 20:09

$a^{-1}$ does not exist when a is a divisor of zero. It follows because of $55=5\cdot11$ and $66=2\cdot3\cdot11$ thah the smallest positive is $11$ in both rings, modulo $55$ and $66$

A modular inverse is not defined if it isn't relatively prime to the modulus. In this case, 11 is not relatively prime to 55 or 66, so it's a value that works. However, the factors of 55 are 11 and 5, and factors of 66 are 2, 3, and 11. If a = 10, which has a factorization of 2 * 5, then it's the smallest possible value of a that works, not 11.