Factoring Method: Learn How to Use It

In summary, the conversation discusses a college project on factorization techniques and the search for an original method. The proposed method is based on finding a congruence of squares and using multiplication and subtraction to factorize numbers. The conversation also mentions the use of excel and the desire to test the method on larger numbers using programming languages such as C or Python. The method is compared to other known factorization methods.
  • #1
Jopus
1
0
Hello,

I'm currently learning all about factorization techniques for a college project. I know that most of the advanced techniques are based around a congruence of squares. As part of our research we've been asked to think up an original factoring method. It doesn't matter how slow or fast it is as long as its original, and we get bonus points for this if we can prove it's original. I have thought of a method, although I don't think it is original, but I'm not sure, so I've come on here to check.

I'll give the method with some examples which I've been working through in excel. Tbh I've been working through many examples, and I've hit the number limit with excel which is above 10 digits or something.

Anyway, here goes:

Example (1): Factorize the number 77.

Method: 77 = 8^2 + 13
13-8 = 5, 5^2 + 4.13 = 77

Now we have that 77 = 8^2 + 1.13 ...(1)
and 77 = 5^2 + 4.13 ...(2)

Now multiply (1) by 2^2, giving 308 = 16^2 + 4.13 ...(3)

Then subtract (2) from (3) giving 231 = 16^2 - 5^2

Then factorise 77 as gcd(77, 16-5)*gcd(77,16+5) i.e. 77 = 11 * 7

Example (2): Factorize the number 8791.

Unlike with 77, which worked on the first attempt, this only works at the third attempt. Each attempt multiply the number in question by 1,2,3,4,5...

So attempts 1 and 2 didn't result in a square being generated, but attempt 3 does:

3*8791 = 26373 = 162^2 + 129

Now do Abs(129 - 162) = 33

33^2 + 196.129 = 26373

So we have that: 162^2 + 1.129 = 26373 ...(1)
33^2 + 196.129 = 26373 ...(2)

Now multiply 1 by 14^2 (=196) to give: 2268^2 + 196.129 = 196.26373 ...(3)
And: 33^2 + 196.129 = 26373

Subtracting (2) from (3) gives: 2268^2 -33^2 = 195.26373

Thus 8791 = gcd(2268-33, 8791)*gcd(2268+33,8791) = 149 * 59

Example (3): Factorize 8414786257.

A square was found in excel at the 1496th attempt.

1496*8414786257 = 3548030^2 + 3359572 = 188458^2 + 3736489.3359572

i.e. 1496*8414786257 = 3548030^2 + 3359572 = 188458^2 + (1933^2).3359572

Thus gcd(1933.3548030-188458, 8414786257) = 104297
and gcd(1933.3548030+188458, 8414786257) = 80681 Q.E.D.

I hope someone will be able to give me some feedback on this. As I say, I don't think this method can possibly be fully original, but I may get partial credit for any original element? Thanks for your help in this. :D

I'm running into a bit of a problem with excel, because of floating point integers and the limits with representation. I'd like to test out this method on larger integers, maybe using C. I'm a bit rusty on it at the moment, so if anyone could implement it fairly quickly and let me know how the results shape up I'd be grateful. I've reached the limit with what can be done with excel. This is the largest number I've been able to factorize thus far: 30,436,307,070,163. It's only 14 digits long. I want to test this method with semiprime numbers up to 20 or 30 decimal digits at least. 30,436,307,070,163 was factorized as follows.

At the 10,560th attempt a square was found:

10,560*30,436,307,070,163 = 566,928,040^2 + 122,679,680 = 444,248,360^2 + (31,799^2)*122,679,680

Thus gcd(31,799*566,928,040-444,248,360; 30,436,307,070,163) = 8,589,337.
The other factor is gcd(31,799*566,928,040+444,248,360; 30,436,307,070,163) = 3,543,499

From previous posts on this site, I've seen somewhere that a method must be tested for numbers greater than 2^64 to see if it is truly effective, and this falls well short of that, which is about 20 decimal digits, although this last factorization is much better than trial division, since sqrt(30,436,307,070,163) = 5,516,911 and there are about 382,000 primes below this number, hence 10,560 attempts is not bad at this stage. However I think this will be insufficient as the numbers grow larger, but I have no idea as I lack the ability to test this out on C at the moment. If anyone could quickly check this out by seeing how it performs with two 15 digit primes, spaced not too close together, I would be very grateful to them.
 
Physics news on Phys.org
  • #2
you write:
5^2 + 4.13 =77
that's wrong. 5^2 + 4.13 =25+4.13 =29.13

same thing with your equations 1 and 2. How can 77 be equal to 8^2 + 1.13 ?

and what exactly do you mean by ... in equation 1 and 2?
 
  • #3
epsi00 said:
you write:
5^2 + 4.13 =77
that's wrong. 5^2 + 4.13 =25+4.13 =29.13

same thing with your equations 1 and 2. How can 77 be equal to 8^2 + 1.13 ?

and what exactly do you mean by ... in equation 1 and 2?
Its pretty obvious that the period stands for the multiplication sign. You can take that approach when you have a given that you are not working with decimals. However, I think that the op could have used the more conventional * to make it more clear.
 
  • #4
I havn't seen this method of factoring before. However, proving it original may be a problem. You may try the wolfram site to work math problems with large numbers.
 
Last edited:
  • #5
It seems to me that it is a modified form of Fermat factoring. A^2 - B^2 Is the next to the last step.
 
  • #6
coolul007 said:
It seems to me that it is a modified form of Fermat factoring. A^2 - B^2 Is the next to the last step.
It's a precursor to Dixon's method.

Jopus said:
I'd like to test out this method on larger integers, maybe using C.
Python is probably a better choice; it has arbitrary precision integers built-in, and is generally easier to program in.
 
  • #7
C as well as JAVA have the BigInterger type, fairly easy to use.
 
  • #8

Related to Factoring Method: Learn How to Use It

What is the factoring method?

The factoring method is a mathematical process used to break down a polynomial expression into simpler components, making it easier to solve. It involves finding the greatest common factor and using it to divide the expression into smaller terms.

Why is the factoring method important?

The factoring method is important because it helps simplify complex mathematical expressions and allows for easier problem solving. It can also be used to find the roots of a polynomial equation, which is useful in many real-world applications.

What are the steps involved in using the factoring method?

The steps involved in using the factoring method are:

  1. Identify the greatest common factor (GCF) of the polynomial expression.
  2. Factor out the GCF from the expression.
  3. Use the distributive property to expand the expression and check if it matches the original expression.
  4. If the expression does not match, continue factoring using other methods such as grouping or the difference of squares.
  5. Once the expression is completely factored, solve for the variables.

What are some common mistakes when using the factoring method?

Some common mistakes when using the factoring method include:

  • Forgetting to factor out the GCF first.
  • Incorrectly applying the distributive property.
  • Not checking if the factored expression matches the original expression.
  • Using the wrong factoring method for a specific polynomial expression.

Can the factoring method be used for all types of polynomial expressions?

Yes, the factoring method can be used for all types of polynomial expressions, including trinomials, binomials, and polynomials with more than three terms. However, some expressions may require different factoring methods, such as the difference of squares, to be fully factored.

Similar threads

Replies
4
Views
1K
  • Introductory Physics Homework Help
Replies
11
Views
780
  • Calculus and Beyond Homework Help
Replies
3
Views
635
  • Engineering and Comp Sci Homework Help
2
Replies
39
Views
3K
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • STEM Educators and Teaching
Replies
2
Views
12K
  • Precalculus Mathematics Homework Help
Replies
7
Views
3K
  • Precalculus Mathematics Homework Help
Replies
1
Views
876
  • Linear and Abstract Algebra
Replies
7
Views
6K
Back
Top