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?