# COdeBook S.4 Shor's algorithm

**URL:** <https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749>\
**Category:** Codebook\
**Created:** [March 22, 2023, 8:32am UTC](https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749 "2023-03-22T08:32:01Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mayu](https://yyz2.discourse-cdn.com/flex012/user_avatar/discuss.pennylane.ai/mayu/32/3328_2.png) [@Mayu](https://discuss.pennylane.ai/u/Mayu)\
**Post date:** [March 22, 2023, 8:32am UTC](https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749/1 "2023-03-22T08:32:01Z")

</div>

![image](https://canada1.discourse-cdn.com/flex012/uploads/pennylane/original/2X/f/fa9503122fd4a737642532902bb09f23ea5d0f28.png)

Is “not coprime” a mistake as “coprime” in step 2?

---

<div class="post-metadata">

**Author:** ![CatalinaAlbornoz](https://yyz2.discourse-cdn.com/flex012/user_avatar/discuss.pennylane.ai/catalinaalbornoz/32/1196_2.png) [@CatalinaAlbornoz](https://discuss.pennylane.ai/u/CatalinaAlbornoz)\
**Post date:** [March 24, 2023, 8:41pm UTC](https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749/2 "2023-03-24T20:41:50Z")

</div>

Hi @Mayu,

It depends in how you’re looking at the question but I agree that the wording may be a little confusing here. Let me try to clarify this a bit:

If they are not coprime then you can easily find the factors and if they are coprime then you continue with the algorithm.

Note that if they’re not coprime then the Greatest Common Denominator (GCD) between **N** and **a** is going to be larger than 1, so this means we obtain a common factor that is one of the prime factors we are looking for.  
Eg: we want to factor **N** =21. We choose **a** =6. We find that GCD(N,a)=3. So 3 is one of the factors of 21. To calculate the other factor we can do 21/3=7.

If you look at the Codebook’s explanation below this list you will find some more details on why we check whether **a** and **N** are or not coprime.

![image](https://canada1.discourse-cdn.com/flex012/uploads/pennylane/original/2X/c/c89c3805331207beafac3cbe087fcf056ca73759.png)

Thank you for posting this question here. We will review the wording to make sure that it’s more clear 🙂

---

<div class="post-metadata">

**Author:** ![Mayu](https://yyz2.discourse-cdn.com/flex012/user_avatar/discuss.pennylane.ai/mayu/32/3328_2.png) [@Mayu](https://discuss.pennylane.ai/u/Mayu)\
**Post date:** [March 24, 2023, 11:56pm UTC](https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749/3 "2023-03-24T23:56:47Z")

</div>

Thank you, Catalina! I understand it very cleary! 😀

---

<div class="post-metadata">

**Author:** ![CatalinaAlbornoz](https://yyz2.discourse-cdn.com/flex012/user_avatar/discuss.pennylane.ai/catalinaalbornoz/32/1196_2.png) [@CatalinaAlbornoz](https://discuss.pennylane.ai/u/CatalinaAlbornoz)\
**Post date:** [March 28, 2023, 6:10pm UTC](https://discuss.pennylane.ai/t/codebook-s-4-shors-algorithm/2749/4 "2023-03-28T18:10:09Z")

</div>

I’m glad this was clear for you @Mayu! Thank you for asking the question.