# Tagged Questions

25 views

### How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
55 views

47 views

### Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
200 views

### How to reverse modulo of a multiplication?

I am primarily a programmer (rather than a mathematician) and have recently come across a coding problem where I must invert a function which is the the modulo of a multiplication (given certain ...
151 views

### Inverse modulo question?

I know that when gcd(a,b) = 1, a and b are relatively prime. This allows you to write the linear combination aS + bT = 1, where S and T are Bezouts's coefficients. As I understand, one of these ...
26 views

### Calculate inverse modulo: $8^{-13}\pmod {29}$

How can I calculate $8^{-13}\pmod{29}$ ? I don't get how it works. Can I do it separately? So first $8^{-13}$ and then modulo $29$. And how can I calculate a negative power the quickest?
27 views

### Simplify functions involving modular arithmetic

In this question, the answer says that f o g(x) = x. But I am unable to get this result. The expression I am able to get is that f o g(x) = 7*(x mod 3) + 57*(x mod 7) (mod 21). I am unable to ...
110 views

### Computing an inverse modulo $25$

Supposed we wish to compute $11^{-1}$ mod $25$. Using the extended Euclid algorithm, we find that $15 \cdot 25 - 34 \cdot 11 =1$. Reducing both sides modulo $25$, we have $-34 \cdot 11 \equiv 1$ mod ...
33 views

### Inverses of Modulo N

It's easy to show that relatively prime numbers have inverse mod n via the Euclidian Algorithm-How do you show that they don't necessarily have an inverse if they aren't relatively prime? I would ...
### Pairing off residues modulo $p$ with their inverses
I'm stumbling over this interesting proof: Show that if $p$ is a prime number, the positive integers less than $p$, except $1$ and $p-1$, can be split into $(p-3)\over2$ pairs of integers such ...