1. ## Inverse Modulo

a: With justification, find an inverse for 3276 modulo 3025.
b: With justification, find an inverse for 3276 modulo 3026.

I am completely stumped
How can there be a positive integer 's' such that 3276 ∙ s ≡ 1 (mod 3025 (or 3026)) ???

2. Hi
First of all, to have its class inversible modulo $n,$ an integer $m$ has to satisfy the condition : $\text{gcd}(m,n)=1$

Now if $n,m$ are relative primes, then you can use Bezout's algorithm to find $u,v$ integers such that : $un+vm=1.$ Thus you'll have $[1]=[un+vm]=[u][n]+[v][m]=[u][0]+[v][m]=[v][m]$ i.e. the class of $v$ will be your inverse.

3. Hello, starman_dx!

There are a number of streamlined procedures.
I'll show you a primitive algebraic approach.

(a) With justification, find an inverse for 3276 modulo 3025.
We have: . $3276a \:\equiv \:1 \pmod{3025}$

This means: . $3276a \:=\:3025b + 1\:\text{ for some integer }b.$

Solve for $b\!:\;\;b \:=\:\frac{3276a - 1}{3025} \quad\Rightarrow\quad b \:=\:a + \frac{251a - 1}{3025}$

Since $b$ is an integer, $251a - 1$ is a multiple of 3025.

. . That is: . $251a - 1 \:=\:3025c\:\text{ for some integer }c,$

Solve for $a\!:\;\;a \:=\:\frac{3025c + 1}{251} \quad\Rightarrow\quad a \:=\:12c + \frac{13c+1}{251}$ .[1]

Since $a$ is an integer, $13c+1$ is a multiple of 251.

. . That is: . $13c + 1 \:=\:251d\:\text{ for some integer }d.$

Solve for $c\!:\;\;c \:=\:\frac{251d - 1}{13} \quad\Rightarrow\quad c \:=\:19d + \frac{4d-1}{13}$ .[2]

Since $c$ is an integer, $4d-1$ is a multiple of 13.

. . That is: . $4d-1 \:=\:13e\:\text{ for some integer }e.$

Solve for $d\!:\;\;d \:=\:\frac{13e+1}{4} \quad\Rightarrow\quad d \:=\:3e + \frac{e+1}{4}$ .[3]

We see that $d$ is first an integer when $e = 3.$

Substitute into [3]: . $d \:=\:3(3) + \frac{3+1}{4}\quad\Rightarrow\quad d \:=\:10$

Substitute into [2]: . $c \:=\:19(10) + \frac{4(10)-1}{13} \quad\Rightarrow\quad c \:=\:193$

Substitute into [1]: . $a \:=\:12(193) + \frac{13(193) + 1}{251} \quad\Rightarrow\quad a \:=\:2326$

Therefore, the inverse of $3276\:(\text{mod }3025)$ is: . $\boxed{2326}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Check

$(3276)(2326) \;=\;7,\!619,\!876 \;=\;(3025)(2519) + 1$