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

[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?

 

[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)

 

[roger]

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

 

[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.

 

[matt grime]

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

 

[roger]

But that doesn't answer my questions.

 

[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.

 

[CRGreathouse]

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

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

 

[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

 

[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*?

 

[roger]

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'.

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

 

[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.

 

[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?

 

[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?

 

[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.)

 

[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.

 

[roger]

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

 

[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).

 

[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

 

[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.

 

[roger]

No. I don't know in what sense (mathematically) (0,1) and (1,0) are 'different'.

and again, no I don't know the pigeon hole principle.

I asserted that the answer ought to be =>(n^2)+1 because I thought if there were n^2 pairs of residues, then the next term would create a pair which is a duplicate. But there needs to be 2 more terms than n^2 to create a duplicate. Yet I still don't understand how it works.

consider the sequence of integers 2,3,5,8,10,12.

Then mod 2 the sequence goes 0,1,1,0,0,0. Yet there is no 2 pairs of integers here despite the original sequence being greater than n^2+1 terms, in this case 6>5. Why not?

I don't see the relevance of this: '' you need 2 terms to get one pair, 3 terms to get 2 pairs and so on''

Thanks
roger

 

[roger]

By the way, you said earlier '' you need more than n^2+2 terms in the sequence. So > n^2+1 is correct.''

But n^2+2 terms is >n^2+1 but not >n^2+2?

 

[matt grime]

No. I don't know in what sense (mathematically) (0,1) and (1,0) are 'different'.

order, they are ordered pairs

and again, no I don't know the pigeon hole principle.

I asserted that the answer ought to be =>(n^2)+1 because I thought if there were n^2 pairs of residues,

But you just said that you didn't see why (0,1) and (1,0) are different. Now you're using the fact that they are

then the next term would create a pair which is a duplicate.

which is what the pigeon hole principle states.

But there needs to be 2 more terms than n^2 to create a duplicate. Yet I still don't understand how it works.

You have now made two mistakes. Let's see if we can spot them in toy example:

consider the sequence of integers 2,3,5,8,10,12.

Then mod 2 the sequence goes 0,1,1,0,0,0. Yet there is no 2 pairs of integers here despite the original sequence being greater than n^2+1 terms, in this case 6>5. Why not?

the pair (0,0) occurs twice. do you see that? terms 3 and 4, and terms 4 and 5. The sequence goes 0,1,1,0,0,0, so the pairs are 0,1 then 1,1, then 1,0, then 0,0 then 0,0 again 6 terms give 5 pairs: terms 1 and 2, then terms 2 and 3, then... see?

I don't see the relevance of this: '' you need 2 terms to get one pair, 3 terms to get 2 pairs and so on''

Thanks
roger

read posts 16 and 18 again, and this one several times. try to think about what is going on.

 

[roger]

another quick question:

there will be two integers r=/=s such that (a_r,a_{r+1}) = (a_s,a_{s+1})


But doesn't r=s by definition of (a_r,a_{r+1}) = (a_s,a_{s+1})

 

[matt grime]

Of course not. Look at your example. r=3 and s=4.

 

[roger]

another question I have : if n is an integer, and S is the set of residues mod n, how do I know whether a subset of S will add up to 0mod n?

 

[matt grime]

You are allowed to start a new thread with a new question.

The answer is: that depends on the subset. I suppose 'by adding them up' is too obvious an answer?

 

[roger]

won't it become tedious to add up, if n is large?

 

[matt grime]

Then you'd hope to exploit some structure of the set. Since we have no idea what the set is, no, we don't have a clever way of doing it. Let me put it this way: you're asking for the sum of a set of numbers that you're not going to specify in anyway shape or form. Not being mind readers we can't add them up at all, or even begin to offer any advice. And what has tediousness got to do with anything?

 

[CRGreathouse]

It sounds a lot like the subset-sum problem, about which there is substantial literature relating to the cryptographic and complexity theoretic 'applications'.