Aren't Polynomial remainder theorem and Euclid division algorithm different? In polynomial division we subtract powers of $x$ and if the divisor's degree is higher than $2$, say divisor is $x^2+1$ then the remainder will be of type $ax+b$ which exclusively depends upon $x$.

Euclid division of polynomial will result in an equation of the form $p(x) = q(x)s(x) + r(x)$ where $r(x)$ is the remainder. When substituting $x$ for a value $c$ we have that the equation still holds, but now $r(c)$ doesn't have to be the remainder (just a remainder in general). The point is that you reach a equation of the form $2^{99} = 9q(8) - 1$ where $q$ is a polynomial (with integer coefficients).

I also don't get how can the remainder be negative in numerical division, e.g. 33/5 gives remainder 3(i.e. 33-5*6) but if we do 33-(7*5) then we get (-2) as the remainder. But then why does it make sense? Why do 3 and -2 become congurent and help in simplifying calculations?

There's difference between a remainder and the remainder (which is a specific remainder). You have for example $33 = 5\times7-2$, here's $-2$ is a remainder, but normally when talking abouth the remainder one is after the least possible positive remainder, that is the least positive number such that $33 = 5n+r$

but if $q(c)=0$ then $r(c)$ is actually the remainder but still the remainder of polynomial division. How can we show that if q(x) has a degree 1 in x then r(c)[which will obviously be a numeric constant] is same as would be the remainder of Euclid division?

When doing euclid division you will get a remainder that is of degree one less than the denominater. In this example the denominator is $x-(-1)$ that is of degree $1$. So the remainder will be of degree $0$, that is constant. The polynomial remainder theorem says what the remainder polynomial is.

I know that. In our case the remainder of polynomial division a numeric constant. But why is this constant same as would be the remainder of actual Euclid division performed on actual numbers. BTW I could not understand which degree of denominator are you saying in Euclid division.

The

Hello.

The degree of the remainder in euclid division will be at most one lower than the degree of the denominator. For example if it's a second degree polynomial as fx $x^2+1$ the remainder will be first degree polynomial (ie on the form $ax+b$). In the polynomial remainder theorem the denominator is $x-a$ so the remainder will be a polynomial of degree 0 (that is a constant expression).

I got another doubt. Why is the least positive remained of $8^{33}/9$ is same as least positive equivalent remainder of $-1 \bmod 9$. I come to the polynoimial doub first...

Yes I understand that.

The degree will be 0. But still it is the remainder of Polynomial division not Euclid division.

The result you get with euclid division on actual numbers will not need to be the same as you get if you insert numbers into the polynomials, but this was not the goal with the use of polynomial. We were just after a expression of the form $2^{99} = 9q - 1$ from which we can deduce the remainder.

hmm perhaps we are just writing 2^{99} in a form of 9k+r

Ah, Euclid division can be used as a generic term for using the Euclid division algorithm. This can be used on both numbers and polynomial. The algorithm works by working on expressions of the form $a = bq + r$ (by adding to $q$ while you subtract $b$ timas more from $r$) and rearrange that so that $r$ becomes as small as possible.

Yes, that's the point here. Once you've found such an $r$ that is manageable you can step it 9 steps up or down until you're pleased with the result. $9k+r = 9(k-1) + (r+9)$ and so on.

PErhaps I got why the polynomial division is working. But still I'm somewhat confused about 8^{33} is equivalent to (-1) because their difference is divisible by 9. No how do we know that -1=9k+r= 9(-1)+8 and r=8 gives the same r we want.

perhaps there is only a unique least positive r for both -1 mod 9 and 8^33 mod 9.

Yes, $-1=9(-1)+8$, that's probably clear. It can also be shown that there exists only one integer $r$ between 0 and 8 (inclusively) such that $a = 9q + r$, that's the number we normally call the remainder. You know this by knowing that the division algorithm wouldn't be finished unless the remainder is in that interval and you could continue until it is (and then you're finished).

I suppose that we can remove some comments as they probably aren't useful for somebody else?