# How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography.

I have done some exercises with integers number but I have two exercises in which appears algebric expressions and the basic long polynomial's division algorithm seems not to work.

The exercise

are:

#1 Find integers (x, y)that satisfies (5n+3).x + (3n+2) = gdc(5n+3, 3n+2)

Doubt: for some point in the division, I will get a negative quotient if I do the general way but teacher answers only displays positive quotients. I use successive divisions to get the gdc.

# 2 Find integers (x, y) that satisfies (3^2n + 2).x + (3^n + 1).y) = 2.

Doubt: same problem as the first question but in this one I tried to use long polynomial's division algorithm successively but did not accomplished because the given equation is not a polynomial one. One classmate had the idea of finding the the binomial product in first step (3^2n)= (3^n+1).q -2) + rand she found in first steps q = (3^n -1) and r = 3.


How first problem works as I can not get negative quotients but in polynomial's long division I get some?

And what is the process to find solutions for number two? I cannot use polynomial's long division. Is the successives divisions are get in brute force's way (try-error) or exist some algorithm for dealing for this type of expression?

• First question: It works well, $x=-3$ and $y=5$. – André Nicolas May 10 '16 at 20:35
• Easy enough to see a pattern in $(9^n + 2) x + (3^n+1)y = 1$ by solving for $n=1,2,3.$ To get $2$ on the right hand side, just double $x,y.$ – Will Jagy May 10 '16 at 21:17