1
vote
4answers
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 ...
0
votes
1answer
55 views

How do I find the inverse of $e \bmod (p-1)(q-1)$?

I'm trying to find this inverse modulo to set up a solution for an RSA cipher. I haven't the slightest how to go about this. When I looked up the formula for such a question, it states: $$ d \equiv ...
0
votes
2answers
62 views

Use Euclid's Algorithm to find the multiplicative inverse

Use Euclid's Algorithm to find the multiplicative inverse of $13$ in $\mathbf{Z}_{35}$ Can someone talk me through the steps how to do this? I am really lost on this one. Thanks
0
votes
2answers
24 views

Extended Euclidean Algorithm for Modular Inverse

I'm currently learning how to find the inverse of a modulo with the Extended Euclid Algorithm and I stumbled upon a problem when finding an inverse when the $m>p$ as for $m \equiv 1 \pmod{p}$ For ...
0
votes
4answers
38 views

Inverse $2^{18}$ in GF(23) without extended euclidean algorithm

I have a little question about the calculation of the inverse of $2^{18} \mod\ 23$. I have the solution of this: $$ \text{The inverse of $2^{18}$ is $2^{-18}$. The modulus in the exponent is ...
0
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
3answers
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 ...
0
votes
2answers
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 ...
0
votes
2answers
38 views

Explanation of this step in a modular arithmetic problem

The multiplicative inverse of $5$ is $7$, when using mod $34$. $$\begin{align*} 5\cdot x&=3\\[0.1in] 7\cdot 5\cdot x &=7\cdot 3\\[0.1in] 1\cdot x &=7\cdot 3\\[0.1in] x&=21 ...
2
votes
2answers
75 views

Modular Arithmetic Equations

I'm trying to solve $x^{16} = [1]_{989}$ in $x ∈\Bbb Z/989\Bbb Z$. I tried a few simplifications but don't know how to solve it. Any help is welcome.
1
vote
2answers
69 views

Find the inverse of $\alpha^{38}$ in $\mathbb F = \mathbb Z_2[x]/\left<x^4+x+1\right>$

Let $\alpha$ be a root of $x^4+x+1$ and we are given some powers of $\alpha$ as linear combinations of $1,\alpha,\alpha^2$ and $\alpha^3$ $\alpha^4=\alpha+1$ $\alpha^5=\alpha^2+\alpha$ ... (the rest ...
0
votes
3answers
129 views

How to find the inverse of integer $i$ in $\mathbb Z_{n}$

In my understanding, a number $i$ has an inverse $i^{-1}$ in $\mathbb Z_{n}$ if $i\times i^{-1} \equiv 1 \pmod{n}$ e.g.: In $\mathbb Z_{14}$ the inverse of $3$ is $5$ since $3\times5\equiv1\pmod{14}$ ...
1
vote
3answers
3k views

Find the multiplicative inverse of 23 in Z26

I have no number theory training, but I did many google reading prior coming here. There are so many ways to solve this problem but I am lost. How would you find the answer to the question Find the ...
0
votes
1answer
72 views

Calculating $\frac{\,^{n}P_{r}}{q!} \pmod{m}$

For calculating the value of choosing $r$ items from $n$ items where $q$ are of same kind, and we should take modulo $m$, where $m$ is a prime; I used the following relation: $$\frac{\,^{n}P_{r}}{q!} ...
1
vote
1answer
566 views

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