Factorization & Congruence to 4: Proven or Researched?

  • Context: Undergrad 
  • Thread starter Thread starter numbthenoob
  • Start date Start date
  • Tags Tags
    Factorization
Click For Summary

Discussion Overview

The discussion revolves around the properties of factorization and congruence, specifically focusing on numbers congruent to 1 and 3 mod 4. Participants explore whether certain predictive properties hold for these congruences when expressed as products of two factors, and they question the underlying reasons for these properties.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant asks if it has been proven that for a number congruent to 1 mod 4, the difference between its factors is congruent to 0 mod 4, and for a number congruent to 3 mod 4, the difference is congruent to 2 mod 4.
  • Another participant suggests that if one of the factors is 2, the product cannot be congruent to 1 mod 4, implying that only certain cases need to be considered.
  • A participant questions whether the properties of congruences are related to the number 4 being even, a square, or a power of two, and whether larger numbers exhibit similar properties.
  • One participant claims that similar properties can be proven for other moduli, providing an example with semiprimes congruent to 1 and 5 mod 6.
  • Another participant acknowledges that each divisor has its own set of properties that may provide insights into factorization.
  • A later reply mentions that with enough relationships, one could use the Chinese Remainder Theorem (CRT) to find factors, although this is noted to be impractical for larger numbers.

Areas of Agreement / Disagreement

Participants express varying degrees of certainty about the properties of congruences and factorization. While some agree on the existence of properties for specific moduli, there is no consensus on the general applicability or the reasons behind these properties.

Contextual Notes

Limitations include the lack of formal proofs presented in the discussion, dependence on specific cases, and the unresolved nature of whether these properties hold universally or are unique to certain moduli.

Who May Find This Useful

Readers interested in number theory, particularly those exploring properties of congruences and factorization, may find this discussion relevant.

numbthenoob
Messages
10
Reaction score
0
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.
 
Physics news on Phys.org
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.
 
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.
 
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.
 
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.
 
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.
 
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. :-)
 

Similar threads

Graduate What Are the Surrogate Number Congruences for Moduli Other Than Its Factors?
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K
Insights Why Vector Spaces Explain The World: A Historical Perspective
  • · Replies 0 ·
Replies
0
Views
8K
Graduate Plane lattice proof of Leibniz series
  • · Replies 1 ·
Replies
1
Views
3K
Finding the orders of 1, 2, .... , 16 (mod 17)
  • · Replies 1 ·
Replies
1
Views
6K
Graduate Congruence of all integers n, 4^n and 1 +3n mod(9)?
  • · Replies 3 ·
Replies
3
Views
5K
What Are the Two Factors of 15120 Given Their Sum and Difference?
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Congruence Class Relationships in \mathbb{Q}[\sqrt{3}]
  • · Replies 22 ·
Replies
22
Views
6K
Undergrad Has superdeterminism been proven recently?
  • · Replies 3 ·
Replies
3
Views
2K