3
$\begingroup$

Here's the question:

What's the smallest integer > 1 that has a multiplicative inverse modulo 10! (that is, 10 factorial)?

What does that mean?

I understand that:

We say that x is the multiplicative inverse of a modulo N whenever ax = 1(mod N)

But... we only know N in this case right? I'm very confused

$\endgroup$
3
$\begingroup$

You have the right definition. And it is a theorem that $a$ has a multiplicative inverse modulo $m$ if and only if $a$ and $m$ are relatively prime. So what is the smallest integer $a\gt 1$ such that $a$ and $10!$ are relatively prime?

$\endgroup$
  • $\begingroup$ So, if I were to say A has a multiplicative inverse modulo B, this means that there exists an X such that Ax(mod B) = 1 right? $\endgroup$ – Jess Mar 21 '13 at 2:41
  • $\begingroup$ @Jess: Exactly. But in order to answer the specific question, you need some information about which numbers have a multiplicative inverse modulo $m$. These are the $a$'s relatively prime to $m$. In the case of $m=10!$, the first number after $1$ that has an inverse modulo $m$ is $11$, the next is $13$, then $17$, then $19$, then $23$, and so on. They are definitely not all prime, but the first non-prime one is $11^2$. $\endgroup$ – André Nicolas Mar 21 '13 at 2:46
0
$\begingroup$

Hint $\ $ By Bezout, $\rm\ a\ $ is invertible mod $\rm\:n!\:$ iff $\rm\ a\ $ is coprime to $\rm\:n!.\:$ Thus if $\rm\ a>1\:$ then every prime divisor of $\rm\ a\ $ is $\rm\, > n,\:$ e.g. the next prime $\rm\,> n.\:$

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