factorization and 4

numbthenoob

Hi,

Can anyone confirm for me whether it has been proven that:

if a number is congruent to 1 mod 4 and is expressed as the product of two factors, the difference between those factors will always be congruent to 0 mod 4; and that if the number is congruent to 3 mod 4 the difference between two factors is congruent to 2 mod 4.

If it has been proven, or I suppose even researched, what do I google to read up on it?

I can't find a counterexample and I can't figure out why it is and it's driving me nuts. Why does 4 have this predictive property and other divisors don't?

Thanks much.

robert Ihnot

In the case of ab==1 Mod 4, we need only consider the cases. If a==2 or b==2, then the product can not be congruent to one. So in the remaining cases, all that is possible is that a==b and both are congruent to 1 or 3. It's an easy problem.

numbthenoob

So you are saying it's because 4 is a small number with a limited number of cases that just happen to work out that way? I.e., no larger number has the same property because it's too large? Is this property for 4 related to it being even? Square? A power of two? Or is there no general theory on what limitations congruences place on factors?

Sorry to be so thick.

CRGreathouse

You can prove similar properties about any number you like. Semiprimes congruent to 1 mod 6 are the product of two numbers that are 5 mod 6, or they are the product of two numbers that are 1 mod 6; either way, the difference of their factors is 0 mod 6. Semiprimes congruent to 5 mod 6 are the product of a number that is 5 mod 6 and a number that is 1 mod 6, so their difference is 4 mod 6.

numbthenoob

Thanks CR, that's a little more on point for what I was straining to get at in my clumsy awkward way...so each divisor has its own set of properties which may or may not yield clues about what factors it can have...interesting.

CRGreathouse

Yes.

To anticipate the next question: yes, with enough of these you could CRT the results together and find the factor. No, this isn't anywhere close to practical except for tiny numbers.

numbthenoob

Ok, thanks for your insight. Now that I know what relationships to look for, I'm confident that if I dink around with these numbers enough, I'll be able to find them. :-)