Difference between revisions of "Simon's Favorite Factoring Trick"
(→The General Statement) |
|||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
==The General Statement== | ==The General Statement== | ||
− | Simon's Favorite Factoring Trick (SFFT) (made by AoPS user [https://artofproblemsolving.com/community/user/1233 Complex Zeta]) is often used in a Diophantine equation where factoring is needed. The most common form it appears is when there is a constant on one side of the equation and a product of variables with each of those variables in a linear term on the other side. An example would be: <cmath>xy+66x-88y=23333</cmath>where <math>23333=1</math>. (2021 CEMC Galois #4b) | + | Simon's Favorite Factoring Trick (SFFT) (made by AoPS user [https://artofproblemsolving.com/community/user/1233 Complex Zeta]) is often used in a Diophantine equation where factoring is needed. The most common form it appears is when there is a constant on one side of the equation and a product of variables with each of those variables in a linear term on the other side. An example would be: <cmath>xy+66x-88y=23333</cmath>where <math>23333</math> is the constant term, <math>xy</math> is the product of the variables, <math>66x</math> and <math>-88y</math> are the variables in linear terms. |
+ | |||
+ | |||
+ | Let's put it in general terms. We have an equation <math>xy+jx+ky=a</math>, where <math>j</math>, <math>k</math>, and <math>a</math> are integer constants, and the coefficient of xy must be 1(If it is not 1, then divide the coefficient off of the equation.). According to Simon's Favorite Factoring Trick, this equation can be transformed into: <cmath>(x+k)(y+j)=a+jk</cmath> | ||
+ | Using the previous example, <math>xy+66x-88y=23333</math> is the same as: <cmath>(x-88)(y+66)=(23333)+(-88)(66)</cmath> | ||
+ | |||
+ | |||
+ | If this is confusing or you would like to know the thought process behind SFFT, see this eight-minute video by Richard Rusczyk from AoPS: https://www.youtube.com/watch?v=0nN3H7w2LnI. For the thought process, start from https://youtu.be/0nN3H7w2LnI?t=366. | ||
+ | |||
+ | Here is another way to look at it. | ||
+ | |||
+ | Consider the equation <math>xy+5x+6y=30</math>.Let's start to factor the first group out: <math>x(y+5)+6y=30</math>. | ||
+ | |||
+ | How do we group the last term so we can factor by grouping? Notice that we can add <math>30</math> to both sides. This yields <math>x(y+5)+6(y+5)=60</math>. Now, we can factor as <math>(x+6)(y+5)=60</math>. | ||
+ | |||
+ | This is important because this keeps showing up in number theory problems. Let's look at this problem below: | ||
+ | |||
+ | Determine all possible ordered pairs of positive integers <math>(x,y)</math> that are solutions to the equation <math>\frac{4}{x}+\frac{5}{y}=1</math>. (2021 CEMC Galois #4b) | ||
Let's remove the denominators: <math>4y+5x=xy</math>. Then <math>xy-5x-4y=0</math>. Take out the <math>x</math>: <math>x(y-5)-4(y-5)=0+20</math> (notice how I artificially grouped up the <math>y</math> terms by adding <math>4*5=20</math>). | Let's remove the denominators: <math>4y+5x=xy</math>. Then <math>xy-5x-4y=0</math>. Take out the <math>x</math>: <math>x(y-5)-4(y-5)=0+20</math> (notice how I artificially grouped up the <math>y</math> terms by adding <math>4*5=20</math>). | ||
Line 7: | Line 24: | ||
Now, <math>(x-4)(y-5)=20</math> (you can just do SFFT directly, but I am guiding you through the thinking behind SFFT). Now we use factor pairs to solve this problem. | Now, <math>(x-4)(y-5)=20</math> (you can just do SFFT directly, but I am guiding you through the thinking behind SFFT). Now we use factor pairs to solve this problem. | ||
− | Look at all factor pairs of 20: <math>1 | + | Look at all factor pairs of 20: <math>1*20, 2*10, 4*5, 5*4, 10*2, 20*1</math>. The first factor is for <math>x</math>, the second is for <math>y</math>. Solving for each of the equations, we have the solutions as <math>\boxed{(5, 25), (24, 6), (6, 15), (14, 7), (8, 10), (9, 9)}</math>. |
For more info on the solution: https://www.cemc.uwaterloo.ca/contests/past_contests/2021/2021GaloisSolution.pdf | For more info on the solution: https://www.cemc.uwaterloo.ca/contests/past_contests/2021/2021GaloisSolution.pdf |
Latest revision as of 21:24, 28 August 2024
Contents
The General Statement
Simon's Favorite Factoring Trick (SFFT) (made by AoPS user Complex Zeta) is often used in a Diophantine equation where factoring is needed. The most common form it appears is when there is a constant on one side of the equation and a product of variables with each of those variables in a linear term on the other side. An example would be: where
is the constant term,
is the product of the variables,
and
are the variables in linear terms.
Let's put it in general terms. We have an equation , where
,
, and
are integer constants, and the coefficient of xy must be 1(If it is not 1, then divide the coefficient off of the equation.). According to Simon's Favorite Factoring Trick, this equation can be transformed into:
Using the previous example,
is the same as:
If this is confusing or you would like to know the thought process behind SFFT, see this eight-minute video by Richard Rusczyk from AoPS: https://www.youtube.com/watch?v=0nN3H7w2LnI. For the thought process, start from https://youtu.be/0nN3H7w2LnI?t=366.
Here is another way to look at it.
Consider the equation .Let's start to factor the first group out:
.
How do we group the last term so we can factor by grouping? Notice that we can add to both sides. This yields
. Now, we can factor as
.
This is important because this keeps showing up in number theory problems. Let's look at this problem below:
Determine all possible ordered pairs of positive integers that are solutions to the equation
. (2021 CEMC Galois #4b)
Let's remove the denominators: . Then
. Take out the
:
(notice how I artificially grouped up the
terms by adding
).
Now, (you can just do SFFT directly, but I am guiding you through the thinking behind SFFT). Now we use factor pairs to solve this problem.
Look at all factor pairs of 20: . The first factor is for
, the second is for
. Solving for each of the equations, we have the solutions as
.
For more info on the solution: https://www.cemc.uwaterloo.ca/contests/past_contests/2021/2021GaloisSolution.pdf
Applications
This factorization frequently shows up on contest problems, especially those heavy on algebraic manipulation. Usually and
are variables and
are known constants. Sometimes, you have to notice that the variables are not in the form
and
Additionally, you almost always have to subtract or add the
and
terms to one side so you can isolate the constant and make the equation factorable. It can be used to solve more than algebra problems, sometimes going into other topics such as number theory.
Fun Practice Problems
Introductory
- Two different prime numbers between
and
are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?
(Source)
Intermediate
Problem 1
- If
has a remainder of
when divided by
, and
has a remainder of
when divided by
, find the value of the remainder of when
is divided by
.
- icecreamrolls8
Solution
We have solution . Note that
can be factored into
using Simon's Favorite Factoring Trick. Now, look at n. Then, since the problem tells us that
has a remainder of
when divided by 5, we see that the
factor in the
expression has a remainder of
when divided by 5. Now, the
must have a remainder of
when divided by
as well (because then the main expression has a remainder of
when divided by
). Therefore, since 54 has a remainder of
when divided by
,
must have a remainder of
, so that the entire factor has a remainder of
when divided by
.
- icecreamrolls8
Problem 2
are integers such that
. Find
.
(Source)
Solution
Problem 3
(Source) A rectangular floor measures by
feet, where
and
are positive integers with
. An artist paints a rectangle on the floor with the sides of the rectangle parallel to the sides of the floor. The unpainted part of the floor forms a border of width
foot around the painted rectangle and occupies half of the area of the entire floor. How many possibilities are there for the ordered pair
?
Solution:
By Simon's Favorite Factoring Trick:
Since and
are the only positive factorings of
.
or
yielding
solutions. Notice that because
, the reversed pairs are invalid.
Olympiad
- The integer
is positive. There are exactly
ordered pairs
of positive integers satisfying:
Prove that is a perfect square.
Source: British Mathematical Olympiad Round 2 #1 https://bmos.ukmt.org.uk/home/bmo2-2005.pdf