# euclid

Euclidean algorithm for Laurent polynomials

## Syntax

``dec = euclid(A,B)``

## Description

example

````dec = euclid(A,B)` returns an array of structures such that each row of `dec` corresponds to the Euclidean division of the Laurent polynomial `A` by the Laurent polynomial `B`: `A = B*Q + R`, where `Q` is the quotient and `R` is the remainder.```

## Examples

collapse all

Create two Laurent polynomials:

• $A\left(z\right)={z}^{2}+3z+5+7{z}^{-1}$

• $B\left(z\right)=1+2{z}^{-1}$

```cfa = [1 3 5 7]; cfb = [1 2]; lpA = laurentPolynomial(Coefficients=cfa,MaxOrder=2); lpB = laurentPolynomial(Coefficients=cfb);```

Perform Euclidean division of $A\left(z\right)$ by $B\left(z\right)$. Use the helper function `helperPrintLaurent` to print the quotient and remainder polynomials of each Euclidean division.

```dec = euclid(lpA,lpB); numFac = size(dec,1); for k=1:numFac q = helperPrintLaurent(dec(k,1).LP); r = helperPrintLaurent(dec(k,2).LP); fprintf('Euclidean Division #%d\n',k) fprintf('Quotient: %s\n',q) fprintf('Remainder: %s\n \n',r) end```
```Euclidean Division #1 ```
```Quotient: z^(2) + z + 3 ```
```Remainder: + z^(-1) ```
```Euclidean Division #2 ```
```Quotient: z^(2) + z + 3.5 ```
```Remainder: - 0.5 ```
```Euclidean Division #3 ```
```Quotient: z^(2) + 0.75*z + 3.5 ```
```Remainder: + 0.25*z ```
```Euclidean Division #4 ```
```Quotient: 1.125*z^(2) + 0.75*z + 3.5 ```
```Remainder: - 0.125*z^(2) ```

For each Euclidean division, confirm that $A\left(z\right)=B\left(z\right)\phantom{\rule{0.16666666666666666em}{0ex}}\phantom{\rule{0.16666666666666666em}{0ex}}{Q}_{i}\left(z\right)+{R}_{i}\left(z\right)$, where ${Q}_{i}\left(z\right)$ and ${R}_{i}\left(z\right)$ are the quotient and remainder polynomials, respectively, of the ith division.

```for k=1:numFac q = dec(k,1).LP; r = dec(k,2).LP; areEqual = (lpA==lpB*q+r); fprintf('Euclidean Division #%d: %d\n',k,areEqual) end```
```Euclidean Division #1: 1 Euclidean Division #2: 1 Euclidean Division #3: 1 Euclidean Division #4: 1 ```

## Input Arguments

collapse all

Laurent polynomial, specified as a `laurentPolynomial` object.

Laurent polynomial, specified as a `laurentPolynomial` object.

## Output Arguments

collapse all

Euclidean algorithm factors, returned as a N-by-2 structure array, where N ≤ 4 is the number of decompositions. The ith row of `dec` contains one Euclidean division of `A` by `B`:

```A = B*(dec(i,1).LP) + dec(i,2).LP```

where

• `dec(i,1).LP` is the Laurent polynomial corresponding to the quotient.

• `dec(i,2).LP` is the Laurent polynomial corresponding to the remainder.

## Version History

Introduced in R2021b