Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Simon's Favorite Factoring Trick"
m (→‎Applications)
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
'''Simon's Favorite Factoring Trick''' ('''SFFT''') (made by AoPS user [{{SERVER}}/community/user/1233 ComplexZeta] or Dr. Simon Rubinstein-Salzedo) is often used in a [[Diophantine equation]] where factoring is needed. It most commonly appears in equations such as <math>xy+66x-88y = 23333</math> where there is a constant on one side of the equation and on the other side, a product of variables with each of those variables in linear terms.
  
−
== Applications ==
+
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>
−
This factorization frequently shows up on contest problems, especially those heavy on algebraic manipulation. Usually <math>x</math> and <math>y</math> are variables and <math>j,k</math> are known constants. Sometimes, you have to notice that the variables are not in the form <math>x</math> and <math>y.</math> Additionally, you almost always have to subtract or add the <math>x, y,</math> and <math>xy</math> 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.
+
For example, <math>xy+66x-88y=23333</math> is the same as: <cmath>(x-88)(y+66)=(23333)+(-88)(66)</cmath>
 +
 
 +
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:
  
−
== Fun Practice Problems ==
+
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)
−
===Introductory===
 
−
*Two different [[prime number]]s between <math>4</math> and <math>18</math> are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?
 
  
−
<math> \mathrm{(A) \ 22 } \qquad \mathrm{(B) \ 60 } \qquad \mathrm{(C) \ 119 } \qquad \mathrm{(D) \ 180 } \qquad \mathrm{(E) \ 231 }  </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\cdot5=20</math>).
  
−
([[2000 AMC 12/Problem 6|Source]])
+
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.
  
−
===Intermediate===
+
Look at all factor pairs of 20: <math>1\cdot20, 2\cdot10, 4\cdot5, 5\cdot4, 10\cdot2, 20\cdot1</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>.
  
−
==Problem 1==
+
[//cemc.uwaterloo.ca/sites/default/files/documents/2021/2021GaloisSolution.html More info on the solution]
−
*If <math>kn+54k+2n+108</math> has a remainder of <math>3</math> when divided by <math>5</math>, and <math>k</math> has a remainder of <math>1</math> when divided by <math>5</math>, find the value of the remainder when <math>n</math> is divided by <math>5</math>.
 
  
−
<math> \mathrm{(A) \ 1 } \qquad \mathrm{(B) \ 0 } \qquad \mathrm{(C) \ 4 } \qquad \mathrm{(D) \ 2 } \qquad \mathrm{(E) \ 3 }  </math>
 
  
−
- icecreamrolls8
+
== Applications ==
  
−
==Solution==
+
This factorization frequently shows up on contest problems, especially those heavy on algebraic manipulation. Usually <math>x</math> and <math>y</math> are variables and <math>j,k</math> are known constants. Sometimes, you have to notice that the variables are not in the form <math>x</math> and <math>y.</math> Additionally, you almost always have to subtract or add the <math>x, y,</math> and <math>xy</math> 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..................................
−
We have solution <math>\boxed{(D)}</math>. Note that <math>kn+54k+2n+108</math> can be factored into <cmath>(k+2)(n+54)</cmath> using Simon's Favorite Factoring Trick. Now, look at n. Then, since the problem tells us that <math>k</math> has a remainder of <math>1</math> when divided by 5, we see that the <math>(k+2)</math> factor in the <math>(k+2)(n+54)</math> expression has a remainder of <math>3</math> when divided by 5. Now, the <math>(n+54)</math> must have a remainder of <math>1</math> when divided by <math>5</math> as well [3(mod5) x 1(mod5) = 3(mod5)] matching the main expression which has a remainder of <math>3</math> when divided by <math>5</math>. Therefore, since 54 has a remainder of <math>4</math> when divided by <math>5</math>, <math>n</math> must have a remainder of <math>2</math>, so that the entire factor has a remainder of <math>1</math> when divided by <math>5</math>.
 
  
−
- icecreamrolls8
+
== Problems ==
  
−
==Problem 2==
+
=== Introductory ===
−
*<math>m, n</math> are integers such that <math>m^2 + 3m^2n^2 = 30n^2 + 517</math>. Find <math>3m^2n^2</math>.
 
  
−
([[1987 AIME Problems/Problem 5|Source]])
+
* Two different [[prime number]]s between <math>4</math> and <math>18</math> are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?
  
−
==Solution==
+
<math> \mathrm{(A) \ 22 } \qquad \mathrm{(B) \ 60 } \qquad \mathrm{(C) \ 119 } \qquad \mathrm{(D) \ 180 } \qquad \mathrm{(E) \ 231 }  </math>
−
<cmath>m^2 + 3m^2n^2 = 30n^2 + 517</cmath>
 
−
<cmath>(m^2-10)(3n^2+1)=507</cmath>
 
−
<cmath>507=13*39</cmath>
 
−
<cmath>(3n^2+1)=13,(m^2-10)=39</cmath>
 
−
<cmath>3m^2n^2=588</cmath>
 
  
−
==Problem 3==
+
([[2000 AMC 12/Problem 6|Source]])
  
−
([[2008 AMC 12B Problems/Problem 16|Source]]) A rectangular floor measures <math>a</math> by <math>b</math> feet, where <math>a</math> and <math>b</math> are positive integers with <math>b > a</math>. 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 <math>1</math> foot around the painted rectangle and occupies half of the area of the entire floor. How many possibilities are there for the ordered pair <math>(a,b)</math>?
+
=== Intermediate ===
  
−
Solution: <math>A_{outer}=ab</math>
+
* If <math>kn+54k+2n+108</math> has a remainder of <math>3</math> when divided by <math>5</math>, and <math>k</math> has a remainder of <math>1</math> when divided by <math>5</math>, find the value of the remainder when <math>n</math> is divided by <math>5</math>.
  
−
<math>A_{inner}=(a-2)(b-2)</math>
+
<math> \mathrm{(A) \ 1 } \qquad \mathrm{(B) \ 0 } \qquad \mathrm{(C) \ 4 } \qquad \mathrm{(D) \ 2 } \qquad \mathrm{(E) \ 3 }  </math>
  
−
<math>A_{outer}=2A_{inner}</math>
+
- icecreamrolls8
  
−
<math>ab=2(a-2)(b-2)=2ab-4a-4b+8</math>
+
** We have solution <math>\boxed{(D)}</math>. Note that <math>kn+54k+2n+108</math> can be factored into <cmath>(k+2)(n+54)</cmath> using Simon's Favorite Factoring Trick. Now, look at n. Then, since the problem tells us that <math>k</math> has a remainder of <math>1</math> when divided by 5, we see that the <math>(k+2)</math> factor in the <math>(k+2)(n+54)</math> expression has a remainder of <math>3</math> when divided by 5. Now, the <math>(n+54)</math> must have a remainder of <math>1</math> when divided by <math>5</math> as well [3(mod5) x 1(mod5) = 3(mod5)] matching the main expression which has a remainder of <math>3</math> when divided by <math>5</math>. Therefore, since 54 has a remainder of <math>4</math> when divided by <math>5</math>, <math>n</math> must have a remainder of <math>2</math>, so that the entire factor has a remainder of <math>1</math> when divided by <math>5</math>.
  
−
<math>0=ab-4a-4b+8</math>
+
- icecreamrolls8
  
−
By Simon's Favorite Factoring Trick:
+
* <math>m, n</math> are integers such that <math>m^2 + 3m^2n^2 = 30n^2 + 517</math>. Find <math>3m^2n^2</math>.
  
−
<math>8=ab-4a-4b+16=(a-4)(b-4)</math>
+
([[1987 AIME Problems/Problem 5|Source]])
  
−
Since <math>8=1\times8</math> and <math>8=2\times4</math> are the only positive factorings of <math>8</math>.
+
* A rectangular floor measures <math>a</math> by <math>b</math> feet, where <math>a</math> and <math>b</math> are positive integers with <math>b > a</math>. 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 <math>1</math> foot around the painted rectangle and occupies half of the area of the entire floor. How many possibilities are there for the ordered pair <math>(a,b)</math>?
  
−
<math>(a,b)=(5,12)</math> or <math>(a,b)=(6,8)</math> yielding <math>\Rightarrow\textbf{(B)}</math> <math>2</math> solutions. Notice that because <math>b>a</math>, the reversed pairs are invalid.
+
([[2008 AMC 12B Problems/Problem 16|Source]])
  
−
===Olympiad===
+
=== Olympiad ===
  
−
*The integer <math>N</math> is positive. There are exactly <math>2005</math> ordered pairs <math>(x, y)</math> of positive integers satisfying:
+
* The integer <math>N</math> is positive. There are exactly <math>2005</math> ordered pairs <math>(x, y)</math> of positive integers satisfying:
  
 
<cmath>\frac 1x +\frac 1y = \frac 1N</cmath>
 
<cmath>\frac 1x +\frac 1y = \frac 1N</cmath>
Line 67: Line 65:
 
Prove that <math>N</math> is a perfect square.  
 
Prove that <math>N</math> is a perfect square.  
  
−
Solution: https://socratic.org/questions/given-the-integer-n-0-there-are-exactly-2005-ordered-pairs-x-y-of-positive-integ
+
[//bmos.ukmt.org.uk/home/bmo2-2005.pdf Source]
  
−
Source: British Mathematical Olympiad Round 2 #1 https://bmos.ukmt.org.uk/home/bmo2-2005.pdf
+
== See Also ==
  
−
== See More==
 
 
* [[Algebra]]
 
* [[Algebra]]
 
* [[Factoring]]
 
* [[Factoring]]
 +
 +
=== External Links ===
 +
 +
* [{{SERVER}}/videos/algebra1/chapter11/346 Video on AoPS]
  
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 
[[Category:Theorems]]
 
[[Category:Theorems]]

Revision as of 18:28, 26 April 2025

Simon's Favorite Factoring Trick (SFFT) (made by AoPS user ComplexZeta or Dr. Simon Rubinstein-Salzedo) is often used in a Diophantine equation where factoring is needed. It most commonly appears in equations such as $xy+66x-88y = 23333$ where there is a constant on one side of the equation and on the other side, a product of variables with each of those variables in linear terms.

Let's put it in general terms. We have an equation $xy+jx+ky=a$, where $j$, $k$, and $a$ 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: \[(x+k)(y+j)=a+jk\] For example, $xy+66x-88y=23333$ is the same as: \[(x-88)(y+66)=(23333)+(-88)(66)\]

Here is another way to look at it.

Consider the equation $xy+5x+6y=30$.Let's start to factor the first group out: $x(y+5)+6y=30$.

How do we group the last term so we can factor by grouping? Notice that we can add $30$ to both sides. This yields $x(y+5)+6(y+5)=60$. Now, we can factor as $(x+6)(y+5)=60$.

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 $(x,y)$ that are solutions to the equation $\frac{4}{x}+\frac{5}{y}=1$. (2021 CEMC Galois #4b)

Let's remove the denominators: $4y+5x=xy$. Then $xy-5x-4y=0$. Take out the $x$: $x(y-5)-4(y-5)=0+20$ (notice how I artificially grouped up the $y$ terms by adding $4\cdot5=20$).

Now, $(x-4)(y-5)=20$ (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: $1\cdot20, 2\cdot10, 4\cdot5, 5\cdot4, 10\cdot2, 20\cdot1$. The first factor is for $x$, the second is for $y$. Solving for each of the equations, we have the solutions as $\boxed{(5, 25), (24, 6), (6, 15), (14, 7), (8, 10), (9, 9)}$.

More info on the solution


Applications

This factorization frequently shows up on contest problems, especially those heavy on algebraic manipulation. Usually $x$ and $y$ are variables and $j,k$ are known constants. Sometimes, you have to notice that the variables are not in the form $x$ and $y.$ Additionally, you almost always have to subtract or add the $x, y,$ and $xy$ 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..................................

Problems

Introductory

  • Two different prime numbers between $4$ and $18$ are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?

$\mathrm{(A) \ 22 } \qquad \mathrm{(B) \ 60 } \qquad \mathrm{(C) \ 119 } \qquad \mathrm{(D) \ 180 } \qquad \mathrm{(E) \ 231 }$

(Source)

Intermediate

  • If $kn+54k+2n+108$ has a remainder of $3$ when divided by $5$, and $k$ has a remainder of $1$ when divided by $5$, find the value of the remainder when $n$ is divided by $5$.

$\mathrm{(A) \ 1 } \qquad \mathrm{(B) \ 0 } \qquad \mathrm{(C) \ 4 } \qquad \mathrm{(D) \ 2 } \qquad \mathrm{(E) \ 3 }$

- icecreamrolls8

    • We have solution $\boxed{(D)}$. Note that $kn+54k+2n+108$ can be factored into \[(k+2)(n+54)\] using Simon's Favorite Factoring Trick. Now, look at n. Then, since the problem tells us that $k$ has a remainder of $1$ when divided by 5, we see that the $(k+2)$ factor in the $(k+2)(n+54)$ expression has a remainder of $3$ when divided by 5. Now, the $(n+54)$ must have a remainder of $1$ when divided by $5$ as well [3(mod5) x 1(mod5) = 3(mod5)] matching the main expression which has a remainder of $3$ when divided by $5$. Therefore, since 54 has a remainder of $4$ when divided by $5$, $n$ must have a remainder of $2$, so that the entire factor has a remainder of $1$ when divided by $5$.

- icecreamrolls8

  • $m, n$ are integers such that $m^2 + 3m^2n^2 = 30n^2 + 517$. Find $3m^2n^2$.

(Source)

  • A rectangular floor measures $a$ by $b$ feet, where $a$ and $b$ are positive integers with $b > a$. 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 $1$ foot around the painted rectangle and occupies half of the area of the entire floor. How many possibilities are there for the ordered pair $(a,b)$?

(Source)

Olympiad

  • The integer $N$ is positive. There are exactly $2005$ ordered pairs $(x, y)$ of positive integers satisfying:

\[\frac 1x +\frac 1y = \frac 1N\]

Prove that $N$ is a perfect square.

Source

See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Simon%27s_Favorite_Factoring_Trick&oldid=247403"