2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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'$.

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

$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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.