are the number 5309 and 3072 prime to each other?

Answer 1

5309 divided by 3072 = 1 with remainder of 2237
3072 divided by 2237 = 1 with remainder of 835
2237 divided by 835 = 2 with remainder of 567
835 divided by 567 = 1 with remainder of 268
567 divided by 268 = 2 with remainder of 41
268 divided by 41 = 6 with remainder of 22
41 divided by 22 = 1 with remainder of 19
22 divided by 19 = 1 with remainder of 3
19 divided by3 = 6 with a remainder of 1

Having found a remainder of 1 (before finding a 0) shows that the two numbers are relatively prime. Although this method does not look too efficient, it works every time AND can be easily programmed to let a computer do the work.

If we had found a remainder of 0, then the previous remainder is a common divisor.

e.g., let's try 5305 and 3075
5305 divided by 3075 = 1 with a remainder of 2230
3075 divided by 2230 = 1 with a remainder of 845
2230 divided by 845 = 2 with a remainder of 540
845 divided by 540 = 1 with a remainder of 305
540 divided by 305 = 1 with a remainder of 235
305 divided by 235 = 1 with a remainder of 70
235 divided by 70 = 3 with a remainder of 25
70 divided by 25 = 2 with a remainder of 20
25 divided by 20 = 1 with a remainder of 5
20 divided by 5 = 4 with a remainder of 0

Having found 0, we go up one line and find the last remainder '5' which is common to both numbers.

Answer 2

No. (Edit: By "no" I of course mean "yes", as in they are mutually prime -- no common factors. :) )

3072 is the easier number to factor. 3072 = 3 * 1024 = 3 * 2^10. So, to determine if 5309 and 3072 are mutually prime, we only need to see if 5309 divides 2 or 3, which it doesn't.

* * * * *

By the way, Raymond's technique is also very good. When you can factor at least one of the numbers (as in this case), the factoring approach generally gets you the answer faster. However, if you have two very large numbers where the factoring is difficult, the method described by Raymond gives you the result without factoring.

Answer 3

What do u wana ask??????

Answer 4

uhh......no