Quantum_Shor's

 The IBMLearning code for Shor's Algorithm:

*     *     *

Copilot's Walkthrough:

                                                                                    

                                                                       *     *     *

I was asked for further explanations on the notion of order of a number. It is from Number

Theory:

Understanding the Order of a Number

In number theory, the order of a number refers to its behavior under modular arithmetic, particularly within the context of a multiplicative group of integers modulo n. The order of an integer a modulo n, denoted as "ord_n(a)," is defined as the smallest positive integer k such that:

a^k ≡ 1 (mod n)

This means that when a is raised to the power k and the result is divided by n, the remainder is 1.

Example: Order of 3 Modulo 7

Let’s consider a = 3 and n = 7 to illustrate this concept.

To find the smallest k such that 3^k ≡ 1 (mod 7), we calculate the powers of 3 modulo 7:

3^1 = 3 ≡ 3 (mod 7)

3^2 = 9 ≡ 2 (mod 7)

3^3 = 27 ≡ 6 (mod 7)

3^4 = 81 ≡ 4 (mod 7)

3^5 = 243 ≡ 5 (mod 7)

3^6 = 729 ≡ 1 (mod 7)

Since 3^6 ≡ 1 (mod 7) and there is no smaller exponent for which this is true, the order of 3 modulo 7 is:

ord_7(3) = 6

The order of a number provides valuable information about its cyclic behavior under multiplication modulo n. In this example, 3 has an order of 6, meaning it takes six multiplications of 3 before reaching the equivalent of 1 under modulo 7.

                                                         *     *     *

Finding the Order of 4 Modulo 15

Now, let’s determine the order of a = 4 modulo n = 15. We will find the smallest positive integer k such that:

4^k ≡ 1 (mod 15)

Calculating the powers of 4 modulo 15:

Calculate 4^1:

4^1 = 4 ≡ 4 (mod 15)

Calculate 4^2:

4^2 = 16 ≡ 1 (mod 15)

Since 4^2 ≡ 1 (mod 15), we can stop here.

Conclusion

The smallest positive integer k for which 4^k ≡ 1 (mod 15) is k = 2. Therefore, the order of 4 modulo 15 is:

ord_15(4) = 2