Finding GCD of $95$ and $39$ My Algebra instructor gave us this problem which is to find gcd of $95$ and $39$ and express it as $95x+39y$.  Also are $x$, $y$ unique?
Now they are relatively prime so GCD is $1$.  I have no clue how to find $x$ and $y$ and if they are unique or not.
Thanks!
 A: $x,y$ is not unique.
To avoid long odyssey of Extended Euclidean Algorithm, 
One way to find $x,y$ is to use some technique called substituting value:
Since $gcd(95,39) = 1$[1], $95 x + 39 y = 1$ there exists $x,y \in Z$, Bezout's theorem comes in handy.
Then $95x \equiv 1 \pmod {39} \implies x \equiv 23 \pmod {39} $. [2]
Let $x = 23$, then $95 \times 23 + 39y = 1 \implies y = -56$
For generalisation, $x = 23 + 39k$ then $95 \times (23+39k) + 39y = 1 \implies y = -56 -95k$  forall $k \in Z$ 
EDIT:
The reason why statement[1] holds is that $95 = 5\times19$ and $39 = 3 \times 13$.
The reason why calculation[2] holds is that $95^{-1} \equiv 95^{\phi(39)-1}  \equiv  95^{23} \pmod {39} $ by Fermat's Little theorem.
Because $23 = 2^0 + 2^1 + 2^2 + 2^4 $ and $95^1 \mod 39 = 17$ 
$95^2 \mod 39 = 17 \times 17 \mod 39= 16$
$95^4 \mod 39 = 16\times 16 \mod 39=  22$
$95^8 \mod 39 = 16$
$95^{16} \mod 39 = 22$
$95^{-1} \equiv 22 \times 22 \times 16 \times 17 \equiv 23 \pmod {39}  $
A: HINT.- I think your instructor has asked about the equation $$95x+39y=1$$ (there are always integer solutions when $\gcd(x,y)=1$,  Bezout's theorem). If this is the case, you can find a particular solution, for example $(-16,39)$, so you have
$$95x+39y=1\\95\cdot(-16)+39\cdot39=1$$ hence $$95(x+16)+39(y-39)=0$$ and the general solution is with $n$ integer arbitrary $$\begin{cases}x=-39n-16\\y=39+95n\end{cases}$$
A: Although you could use the extended Euclidean algorithm to calculate that value, sometimes it's simpler to use Euler's theorem and exponentiation by squaring.
I don't want to solve your problem for you, so I will use similar numbers $94$ and $51$ instead.
More precisely, say we want to find $x$ and $y$ such that $94x+51y = \gcd(94,51) = 1$. This implies that $94x=1 \pmod{51}$, thus 
\begin{align}
x & = 94^{\phi(51)-1}    &\pmod{51} \\
  & = 94^{(17-1)(3-1)-1} &\pmod{51} \\
  & = 94^{31}            &\pmod{51} \\
  & = 94^{30+1}    &\pmod{51} \\
  & = 94\cdot(94^{15})^2 &\pmod{51} \\
  & = 94\cdot(94\cdot(94\cdot(94\cdot (94\cdot1^2)^2)^2)^2)^2 &\pmod{51} \\
  & = 94\cdot(94\cdot(94\cdot(94\cdot (94\cdot1^2)^2)^2)^2)^2 &\pmod{51} \\
  & = 19 &\pmod{51}
\end{align}
That means we can pick any $x = 19 \pmod{51}$ to get a solution. For example when $x = 19$ then $94\cdot 19 + 51y = 1$ gets us $y = \frac{1-94\cdot 19}{51} = -35$. On the other hand if $x = 19+51 = 70$ then $y=-129$.
I hope this helps $\ddot\smile$
