Difference between revisions of "Simon's Favorite Factoring Trick"

(Solution)
 
(39 intermediate revisions by 28 users not shown)
Line 1: Line 1:
 
==The General Statement==
 
Simon's Favorite Factoring Trick (SFFT) 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 extortive 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.
 
  
 
== Applications ==
 
== Applications ==
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. Also, it is typically necessary to add the <math>jk</math> term to both sides to perform the factorization.
+
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.
  
 
== Fun Practice Problems ==
 
== Fun Practice Problems ==
Line 22: Line 12:
  
 
===Intermediate===
 
===Intermediate===
 +
 
==Problem 1==
 
==Problem 1==
*If <math>kn+54k+2n+108</math> has a remainder of <math>4</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 of when <math>n</math> is divided by <math>5</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> \mathrm{(A) \ 5 } \qquad \mathrm{(B) \ 7 } \qquad \mathrm{(C) \ 4 } \qquad \mathrm{(D) \ 2 } \qquad \mathrm{(E) \ 3 }  </math>
+
<math> \mathrm{(A) \ 1 } \qquad \mathrm{(B) \ 0 } \qquad \mathrm{(C) \ 4 } \qquad \mathrm{(D) \ 2 } \qquad \mathrm{(E) \ 3 }  </math>
  
 
- icecreamrolls8
 
- icecreamrolls8
  
 
==Solution==  
 
==Solution==  
We have solution <math>3</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>3</math> when divided by <math>5</math> as well (because then the main expression has a remainder of <math>4</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>3</math>, our answer, so that the entire factor has a remainder of <math>3</math> when divided by <math>5</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>.
  
 
- icecreamrolls8
 
- icecreamrolls8
 
Is this really the best place to put this problem? In addition to being wrong, it makes a large jump, simply 'noting' that the equation can be factored a certain way, instead of explaining how to factor it. In my experience, this is the hardest part of learning Simon's Favorite Factoring Trick, and you skip through it. Also, please replace '(first number) has a remainder of (second number) when divided (third number)' with <math>\textrm{(first number)}\%\textrm{(second number)}=\textrm{(third number)}.</math> I might also suggest moving this to a page on modulos. (or create one if it doesn't exist).
 
  
 
==Problem 2==
 
==Problem 2==
Line 40: Line 29:
  
 
([[1987 AIME Problems/Problem 5|Source]])
 
([[1987 AIME Problems/Problem 5|Source]])
 +
 +
==Solution==
 +
<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==
 +
 +
([[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>?
 +
 +
Solution: <math>A_{outer}=ab</math>
 +
 +
<math>A_{inner}=(a-2)(b-2)</math>
 +
 +
<math>A_{outer}=2A_{inner}</math>
 +
 +
<math>ab=2(a-2)(b-2)=2ab-4a-4b+8</math>
 +
 +
<math>0=ab-4a-4b+8</math>
 +
 +
By Simon's Favorite Factoring Trick:
 +
 +
<math>8=ab-4a-4b+16=(a-4)(b-4)</math>
 +
 +
Since <math>8=1\times8</math> and <math>8=2\times4</math> are the only positive factorings of <math>8</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.
  
 
===Olympiad===
 
===Olympiad===
Line 49: Line 67:
 
Prove that <math>N</math> is a perfect square.  
 
Prove that <math>N</math> is a perfect square.  
  
Source: (British Mathematical Olympiad Round 3, 2005)
+
Solution: https://socratic.org/questions/given-the-integer-n-0-there-are-exactly-2005-ordered-pairs-x-y-of-positive-integ
 +
 
 +
Source: British Mathematical Olympiad Round 2 #1 https://bmos.ukmt.org.uk/home/bmo2-2005.pdf
  
 
== See More==
 
== See More==

Latest revision as of 12:13, 8 December 2024

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.

Fun Practice 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

Problem 1

  • 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

Solution

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

Problem 2

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

(Source)

Solution

\[m^2 + 3m^2n^2 = 30n^2 + 517\] \[(m^2-10)(3n^2+1)=507\] \[507=13*39\] \[(3n^2+1)=13,(m^2-10)=39\] \[3m^2n^2=588\]

Problem 3

(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)$?

Solution: $A_{outer}=ab$

$A_{inner}=(a-2)(b-2)$

$A_{outer}=2A_{inner}$

$ab=2(a-2)(b-2)=2ab-4a-4b+8$

$0=ab-4a-4b+8$

By Simon's Favorite Factoring Trick:

$8=ab-4a-4b+16=(a-4)(b-4)$

Since $8=1\times8$ and $8=2\times4$ are the only positive factorings of $8$.

$(a,b)=(5,12)$ or $(a,b)=(6,8)$ yielding $\Rightarrow\textbf{(B)}$ $2$ solutions. Notice that because $b>a$, the reversed pairs are invalid.

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.

Solution: https://socratic.org/questions/given-the-integer-n-0-there-are-exactly-2005-ordered-pairs-x-y-of-positive-integ

Source: British Mathematical Olympiad Round 2 #1 https://bmos.ukmt.org.uk/home/bmo2-2005.pdf

See More