Dividing Modulo Something Only Works When the Numbers Share No Factor
Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators
Daniel Okonkwo — Front-enddeveloper en techredacteur bij OneKitly
Webprestaties · Bestandsformaten
Getoetst aan 2 bronnen
In ordinary arithmetic dividing by three means multiplying by a third. Modular arithmetic has no fractions, so dividing by three means multiplying by whatever number sends three back to one: modulo 7 that number is 5, because 3 × 5 = 15 and 15 leaves remainder 1. Not every number has such a partner. Modulo 8 the number 4 has none at all, because 4 and 8 share the factor 4, and every multiple of 4 is even while 1 is not. The condition is exactly that the two numbers share no factor above one, which is why a prime modulus is so convenient — every non-zero value then has an inverse and division always works.
3 has an inverse modulo 7 — it is 5, since 15 leaves remainder 1. 4 has none modulo 8, because they share the factor 4, and no multiple of 4 ever leaves remainder 1.
Why the shared factor is fatal
If a number and the modulus both divide by four, then every product of that number with anything is a multiple of four, and every remainder it can leave is a multiple of four as well. One is not, so one is unreachable and there is nothing to call an inverse. The argument works for any shared factor and it works both ways: when the greatest common divisor is one, a combination reaching one always exists and the extended Euclidean algorithm produces it. So the test for whether division is possible and the method for performing it are the same computation.
Where the question decides a design
The classic affine cipher multiplies each letter position by a key and adds another, working modulo twenty-six. Decryption needs the multiplier's inverse, so the key has to be coprime with twenty-six — which rules out every even number and every multiple of thirteen, leaving twelve valid choices out of twenty-five. A key of 7 works and its inverse is 15; a key of 13 does not and the message becomes unrecoverable. The same constraint reappears in every scheme where a value is multiplied modulo something and has to be undone later, and it is one of the more common ways a home-made cipher quietly loses information.
| Number and modulus | Common factor | Inverse |
|---|---|---|
| 3 mod 7 | 1 | 5 |
| 7 mod 26 | 1 | 15 |
| 4 mod 8 | 4 | none |
| 6 mod 9 | 3 | none |
Uitgewerkt met onze eigen calculator
Calculator voor de modulaire multiplicatieve inverse
Gegeven
- a
- 3
- Modulus m
- 7
Resultaat
- ggd(a, m)
- 1
Deze cijfers komen uit de calculator hieronder, ze zijn niet met de hand ingetypt — ze worden opnieuw berekend telkens als de tool verandert.
Reken het door met je eigen cijfers →Veelgestelde vragen
- How many numbers have an inverse for a given modulus?
- Exactly as many as Euler's totient counts, which is the same question asked twice. Having an inverse and being coprime to the modulus are the same condition, so the count of invertible values below n is φ(n) by definition. Modulo 26 that is 12, matching the affine cipher's twelve usable multipliers. Modulo a prime it is everything except zero, which is the property that makes prime moduli the default choice whenever a construction needs division to be total.
- Is the inverse unique?
- Unique within the range zero to one less than the modulus, and that qualification is the whole of it. Five is the inverse of three modulo seven, and so are twelve, nineteen and every other number that differs from five by a multiple of seven — they are all the same value as far as the arithmetic is concerned. Tools return the representative in the standard range because a single canonical answer is easier to compare and store, and any other member of the family would work identically in a calculation.
Artikelen die je misschien interesseren
Alle gidsen →Vergelijkbare tools
Bronnen
Een fout in dit artikel gezien?