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

In summary, the conversation revolves around understanding how to factor a number into two coprime numbers and what happens if the number of divisors is odd. The conversation also delves into the concept of consecutive pairs of residues in a sequence of numbers and how it relates to the pigeon hole principle. Despite several attempts to explain the concept, the individual seeking clarification still struggles to fully understand.
  • #1
roger
318
0
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?
 
Mathematics news on Phys.org
  • #2
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
(but this particular case has an even number of divisors(of 3^3 * 5^2 * 7^5) right?)
 
  • #4
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
If you add up the binomial coefficients what do you get?
 
  • #6
But that doesn't answer my questions.
 
  • #7
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
roger said:
(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.
 
  • #9
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
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
matt grime said:
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.)
 
  • #12
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
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
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
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
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

[tex](a_r,a_{r+1}) = (a_s,a_{s+1})[/tex]

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:
  • #17
so could you please explain to me how the result is true?
 
  • #18
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
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
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.
 
  • #21
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
 
  • #22
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?
 
  • #23
roger said:
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.
 
Last edited:
  • #24
another quick question:

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


But doesn't r=s by definition of [tex](a_r,a_{r+1}) = (a_s,a_{s+1})[/tex]
 
  • #25
Of course not. Look at your example. r=3 and s=4.
 
  • #26
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?
 
  • #27
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?
 
  • #28
won't it become tedious to add up, if n is large?
 
  • #29
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?
 
  • #30
It sounds a lot like the subset-sum problem, about which there is substantial literature relating to the cryptographic and complexity theoretic 'applications'.
 
  • #31
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
 
  • #32
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).
 
  • #33
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.
 
  • #34
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
 
  • #35
Have you considered checking a couple of counter examples, with say, p=2 or p=3, or b=0?
 
<h2>1. What does it mean for the mind to go fallow?</h2><p>When we say that the mind has gone fallow, we are referring to a state of mental inactivity or stagnation. It is a term often used to describe a lack of inspiration or creativity.</p><h2>2. How does a fallow mind affect understanding of factoring?</h2><p>A fallow mind can make it difficult to understand factoring because it can hinder our ability to think critically and problem solve. When our minds are not actively engaged, we may struggle to grasp new concepts or make connections between ideas.</p><h2>3. Can a fallow mind be a temporary state?</h2><p>Yes, a fallow mind can be a temporary state. It is often a result of mental fatigue or a lack of stimulation. Taking breaks, engaging in activities that promote creativity, and getting enough rest can help refresh the mind and overcome a state of mental fallowness.</p><h2>4. Are there any benefits to having a fallow mind?</h2><p>While a fallow mind can be frustrating, it can also have some benefits. It allows our brains to rest and recharge, which can improve overall mental well-being. It can also provide a break from constant mental stimulation, allowing us to come back to tasks with a fresh perspective.</p><h2>5. How can I overcome a fallow mind and improve my understanding of factoring?</h2><p>To overcome a fallow mind and improve understanding of factoring, it is important to engage in activities that stimulate the mind, such as reading, solving puzzles, or engaging in creative hobbies. It can also be helpful to take breaks and get enough rest to avoid mental fatigue. Additionally, seeking help from a tutor or mentor can provide additional support and guidance in understanding difficult concepts.</p>

1. What does it mean for the mind to go fallow?

When we say that the mind has gone fallow, we are referring to a state of mental inactivity or stagnation. It is a term often used to describe a lack of inspiration or creativity.

2. How does a fallow mind affect understanding of factoring?

A fallow mind can make it difficult to understand factoring because it can hinder our ability to think critically and problem solve. When our minds are not actively engaged, we may struggle to grasp new concepts or make connections between ideas.

3. Can a fallow mind be a temporary state?

Yes, a fallow mind can be a temporary state. It is often a result of mental fatigue or a lack of stimulation. Taking breaks, engaging in activities that promote creativity, and getting enough rest can help refresh the mind and overcome a state of mental fallowness.

4. Are there any benefits to having a fallow mind?

While a fallow mind can be frustrating, it can also have some benefits. It allows our brains to rest and recharge, which can improve overall mental well-being. It can also provide a break from constant mental stimulation, allowing us to come back to tasks with a fresh perspective.

5. How can I overcome a fallow mind and improve my understanding of factoring?

To overcome a fallow mind and improve understanding of factoring, it is important to engage in activities that stimulate the mind, such as reading, solving puzzles, or engaging in creative hobbies. It can also be helpful to take breaks and get enough rest to avoid mental fatigue. Additionally, seeking help from a tutor or mentor can provide additional support and guidance in understanding difficult concepts.

Similar threads

Replies
6
Views
774
  • General Math
Replies
12
Views
907
  • General Math
Replies
7
Views
1K
  • General Discussion
Replies
15
Views
1K
Replies
2
Views
1K
Replies
1
Views
932
Replies
19
Views
4K
Replies
24
Views
2K
  • General Math
Replies
12
Views
3K
  • General Math
Replies
13
Views
1K
Back
Top