# My mind has gone fallow, and I can't quite understand factoring

1. Dec 10, 2006

### roger

My mind has gone fallow, and I can't quite understand factoring a number into two coprime numbers.

What happens if the number of divisors is odd?

2. Dec 10, 2006

### CRGreathouse

Doesn't matter.

Factor the number into prime powers, put as many prime powers as desired into one factor, and put the rest into the other.

3^3 * 5^2 * 7^5 could be factored into the following coprime pairs:

(1, 3^3 * 5^2 * 7^5)
(3^3, 5^2 * 7^5)
(5^2, 3^3 * 7^5)
(7^5, 3^3 * 5^2)

3. Dec 10, 2006

### roger

(but this particular case has an even number of divisors(of 3^3 * 5^2 * 7^5) right?)

4. Dec 10, 2006

### roger

If my reasoning is right, would the number of coprime pairs be (nC0+...nCn)/2 ? where n is the number of prime factors of the number.

5. Dec 11, 2006

### matt grime

If you add up the binomial coefficients what do you get?

6. Dec 11, 2006

### roger

But that doesn't answer my questions.

7. Dec 11, 2006

### matt grime

Your question has been answered. The number of divisors has nothing to do with whether or not you can write a number as the product of two coprime numbers. You always can: trivially n=n*1.

8. Dec 11, 2006

### CRGreathouse

It would work just the same with 3^3 * 5^2 * 7^4 -- just replace all instances of 7^5 with 7^4.

9. Dec 27, 2006

### roger

Hi guys,

Another thing I'm unsure of is that my book says in any sequence >(n^2)+1 terms, there will at least be two consecutive pairs of residues amongst the terms mod n.
But shouldn't it really be =>(n^2)+1?

Is there an infimum as well as a supremum?

Thankyou for any help.
Roger

10. Dec 28, 2006

### matt grime

I don't think that is what your book says at all. Or at least it is not all it says. Take the sequence a_n=2n. Then mod 4 the sequence goes

0,2,0,2,0,2,0,...

I don't see anything that could be described as a 'consecutive pair of residues'.

Your second question needs elaboration: is there an inf as well as a sup *of what*?

11. Dec 28, 2006

### roger

Actually could you please explain the statement in the book from scratch? (Whatever it's supposed to mean.)

12. Dec 28, 2006

### matt grime

That is impossible if you don't start from scratch. A sequence of what? Integers, are we supposed to guess? Why should we guess that? Begin at the beginning and go on til the end.

13. Dec 28, 2006

### roger

The book doesn't even state what the sequence of numbers should be.

(0,2) in your above example is a consecutive pair isn't it?

14. Dec 28, 2006

### matt grime

What is 'consecutive' about that that is not true of any two numbers? Of course the book states something about what kinds of sequences we must be considering. What is the title of the book? What is the section of the book? What have you been learning in that section? What is the *full* statement of the question with all relevant details? Why do I have to keep asking you for this information?

15. Dec 28, 2006

### roger

But there's no restriction on what the number sequence is. It could be the natural numbers or just randomnly selected numbers. In any case, if it's >(n^2)+1, there will at least be two consecutive pairs of residues amongst the terms mod n. That is all that's written and I merely want to know how it works. (By Consecutive I meant in the sense that if the residues are written down, the number immediately next to another number.)

16. Dec 28, 2006

### matt grime

And why are 0 and 2 consecutive? (Which you asserted above?). I really think you need integers, or there is no chance of applying the pigeon hole principle, which is evidently what you are aiming to do.

It really seems that you should be asking:

given a sequence of residues mod n, a_1, a_2,... then there will be two integers r=/=s such that

$$(a_r,a_{r+1}) = (a_s,a_{s+1})$$

but that at no point is what you've written, and has to be obtained by guessing from your cryptic comments.

In order to have more than n^2+1 pairs, thus allowing us to invoke the pigeon hole principle, you need more than n^2+2 terms in the sequence. So > n^2+1 is correct.

Last edited: Dec 29, 2006
17. Dec 28, 2006

### roger

so could you please explain to me how the result is true?

18. Dec 28, 2006

### matt grime

What part? It is just the pigeon hole principle. There are n^2 possible pairs of residues, mod n. If you have n^2+1 pairs, there is a duplicate. To get at least n^2+1 pairs from considering

(a_1,a_2), (a_2,a_3),..,

you need at least n^2+2 terms (just look - you need 2 terms to get one pair, 3 terms to get 2 pairs and so on).

19. Dec 28, 2006

### roger

sorry I still don't understand where the n^2+1 comes from. I see that the residues 0,1,2 for example can be paired (0,1 ) (1,2) but I don't see the relevance of this.

could you (or anybody else) try to explain it differently?

Thanks,
roger

20. Dec 29, 2006

### matt grime

The pair (0,1) and the pair (1,0) are different - you get that, right? Do you understand the pigeon hole principle? Why did you assert what you thought the answer ought to be if you don't understand the question? For once try answering questions put to you - they are being asked for a reason.