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


#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?

  • $\begingroup$ First question: It works well, $x=-3$ and $y=5$. $\endgroup$ – André Nicolas May 10 '16 at 20:35
  • $\begingroup$ 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.$ $\endgroup$ – Will Jagy May 10 '16 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.