Is Bob right?

Andrew and Bob are writing a computer program which gives the prime factorization of a number.

Andrew suggests the following structure for the program:

User selects an integer, x 0 \bullet\text{ User selects an integer, }x_0 The integer is divided by an integer, y , in ascending order starting from 2 until x 0 = 0 m o d y at which point the program prints y and we find x 1 = x 0 y . \\ \bullet\text{ The integer is divided by an integer, }y \text{, in ascending order starting from 2 until } x_0=0\mod{y} \\ \text{ at which point the program prints } y \text{ and we find } x_1 = \dfrac{x_0}{y}. We repeat the instructions above using x 1 instead of x 0 and upon each iteration finding x n = x n 1 y . \\ \bullet\text{ We repeat the instructions above using }x_1\text{ instead of } x_0\text{ and upon each iteration finding } x_n = \dfrac{x_{n-1}}{y} . The program stops executing when x n is itself prime. \\ \bullet\text{ The program stops executing when } x_n \text{ is itself prime.}

For example,

Let, x 0 = 20 \text{Let, }x_0 = 20

20 = 0 m o d 2 x 1 = 20 2 = 10 20 = {0}\mod{2} \therefore x_1 = \dfrac{20}{2} = 10

Repeating for x 1 , \text{Repeating for } x_1,

10 = 0 m o d 2 x 2 = 10 2 = 5 10 = 0\mod{2} \therefore x_2 = \dfrac{10}{2} = 5

Since x 2 is prime the program stops executing. It has printed out 20 = 2 × 2 × 5. \text{Since } x_2 \text{ is prime the program stops executing. It has printed out } 20 = 2 \times 2 \times 5.

Bob suggests that for some integers, the program would not work as y y would not be prime and so the program would not give the correct factorization.

Is Bob correct?

No Yes

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

If at some point, x n x_n can be divided by a p ap , where a > 1 a > 1 and p 2 p \geq 2 is prime, then we will never check this because division by p p will be checked first.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...