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

 

[roger]

I don't understand what the difference is between bijection and surjection?
I see that f:R->R f(x)=x^2 is epimorphic but I'm not sure about bijection.

Thanks in advance.
Roger

 

[matt grime]

A bijection is a surjection that is also an injection (i.e. look at the definition). Is squaring injective (as a function from R to R)? Obviously not. But then it is not surjective either (since the square of a real number is a positive real number), so you are mistaken in claiming that f above is a surjection (and you should avoid using epimorphism, since it is unnecessarily complicated at this stage).

 

[JonF]

You should look up and go over the definition of bijection and surjection. Or state what you think they mean in your own words. If you really understood them the difference between the two should be evident.

 

[roger]

iff a,b<p where p=prime, a^(p-2)+a^(p-3)b+a^(p-4)b^2...b^(p-2)=0modP?

I know that (a+b)^p-(a^p+b^p)=0modp but I don't know if that's relevant.


Thanks in advance.
Roger

 

[matt grime]

Have you considered checking a couple of counter examples, with say, p=2 or p=3, or b=0?

 

[roger]

Have you considered checking a couple of counter examples, with say, p=2 or p=3, or b=0?

Why would p=2 or 3 be counterexamples?

 

[roger]

it works iff a=/=b and a,b=/=0

 

[matt grime]

Sorry, but this is rubbbish: you have not even clearly stated a proposition. You cannot begin a sentence with if and only if. It makes no sense. And the best guess as to what you are conjecturing is trivially refuted with p=2 or p=3 without thinking very hard. When p=3 it reduces to a+b. So you're honestly attempting to claim that a+b is always 0 mod 3? Nonsense. Just think about it for more than one second and stop wasting people's time.

 

[roger]

When p=3 it reduces to a+b. So you're honestly attempting to claim that a+b is always 0 mod 3? Nonsense. Just think about it for more than one second and stop wasting people's time.

When p=3, given that a,b<p, a=/=b, and a,b=/=0 then a+b=0mod3.
Is that incorrect?

 

[matt grime]

a=2 b=-1? That any good for you? State your question clearly. Are a and b supposed to be integers? residues mod p, what? Since you've used inequalities it can't be a statement about residues since they are not ordered (in any nice way).

 

[roger]

a and b must be positive integers. could you try to explain the proof of it?

 

[roger]

can anybody help me pleae?

 

[matt grime]

It's a geometric progression question, roger. You're supposed to recognise how to simplify

x^n+yx^{n-1}+\ldots y^n

by thinking of geometric progressions. If you don't see why it is a geometric progression, try dividing by something.

 

[roger]

cheers matt.

But why must a and b be <p for it to work?

 

[roger]

a^3+b^5+c^7=d^11 iff a,b,c and d are natural numbers.

Is there a way to simplify this in order to find a,b,c and d?
and is there any significance in the powers being prime?

 

[matt grime]

cheers matt.

But why must a and b be <p for it to work?

What makes you think they must be? Try finding some counter examples and try to spot a pattern. I already gave you many counter examples, and they all had the same theme to them.

 

[matt grime]

a^3+b^5+c^7=d^11 iff a,b,c and d are natural numbers.

This makes no sense, again. You need to write things in sentences, and ones that make sense at that. We keep telling you this.

Are you asking to find the integer solutions to this?

 

[roger]

This makes no sense, again. You need to write things in sentences, and ones that make sense at that. We keep telling you this.

Are you asking to find the integer solutions to this?

I'm asking firstly whether it can be simplified to find a,b,c, and d such that the equality is true, and secondly whether there is any significance in the powers being all prime?

But the 'counter examples you gave were based on any value of a and b whereas afterwards I stated that they must be positive integers.

 

[HallsofIvy]

a^3+b^5+c^7=d^11 iff a,b,c and d are natural numbers.

Is there a way to simplify this in order to find a,b,c and d?
and is there any significance in the powers being prime?

Your first statement is "a^3+ b^5+ c^7= d^11 iff a, b, c, and d are natural numbers". Do you understand that that asserts that a^3+ b^6+ c^7= d^11 for all natural numbers a, b, c, d? It certainly is NOT true since you can take a= b= c= d= 1 and get a false statement.

What you want to say is "Find natural numbers a, b, c, and d such that a^3+ b^5+ c^7= d^11 (or prove that no such numbers exist)".

 

[matt grime]

But the 'counter examples you gave were based on any value of a and b whereas afterwards I stated that they must be positive integers.

I give up. You're on your own.