Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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?

share|improve this answer
    
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? –  Jess Mar 21 '13 at 2:41
    
@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$. –  André Nicolas Mar 21 '13 at 2:46

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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