heureka

3.

Let x and y be integers satisfying 41x+53y=12.
Find the residue of x modulo 53.
(Express your answer as an integer from 0 to 52.)

\(\small{ \begin{array}{|rcl|cl|} \hline 41x+53y &=& 12 \quad |\quad \cdot (-1) \\ -41x-53y &=& -12 \\ -41x &=& -12 +53y \\ \\ \hline \\ -41x &\equiv & -12 \pmod{53} \quad |\quad : (-41) \\\\ x &\equiv & \dfrac{-12}{-41} \pmod{53} \\\\ x &\equiv & \dfrac{12}{41} \pmod{53} \\\\ x &\equiv & 12\cdot 41^{-1} \pmod{53} && 41^{-1} \pmod{53} \quad | \quad \gcd(41,53)=1 \\\\ && &\equiv & 41^{\phi(53)-1} \quad | \quad \phi(53)= 52 \\\\ && &\equiv & 41^{52-1} \pmod{53} \\\\ && &\equiv & 41^{51} \pmod{53} \\\\ && &\equiv & 22 \pmod{53} \\\\ x &\equiv & 12\cdot 22 \pmod{53} \\\\ x &\equiv & 264 \pmod{53} \\\\ \mathbf{x} & \mathbf{\equiv} & \mathbf{52 \pmod{53}} \\ \hline \end{array} }\)

Proof:

\(\begin{array}{|rclr|} \hline 41x+53y &=& 12 \quad & | \quad \pmod{53} \\ 41x \pmod{53}+53y \pmod{53} &=& 12 \pmod{53} \quad & | \quad x \equiv 52 \pmod{53} \\ 41\cdot52 \pmod{53}+\underbrace{53y}_{\equiv 0\pmod{53} } \pmod{53} &=& 12 \pmod{53} \\ 41\cdot52 \pmod{53}+0 &=& 12 \pmod{53} \\ 2132 \pmod{53} &=& 12 \pmod{53} \\ 12 \pmod{53} &=& 12 \pmod{53}\ \checkmark\\ \hline \end{array} \)

Here's the question:

a)

\(\begin{array}{|lrcll|} \hline & y &=& a(x-h)^2 + k \quad & | \quad h = 0,\ k = 5 \\ & y &=& a(x-0)^2 + 5 \\ & \mathbf{y} & \mathbf{=}& \mathbf{ax^2 + 5} \\\\ P(5,4): & 4 &=& a5^2 + 5 \\ & 25a + 5 &=& 4 \\ & 25a &=& 4-5 \\ & 25a &=& -1 \quad & | \quad \\ & a &=& -\frac{1}{25} \\ & a &=& -0.04\\\\ \boxed{y=-0.04x^2+5} \\ \hline \end{array} \)

b)

The highway is on level y = 0

The polynomial $f(x)$ has degree 3. If
$f(-1) = 15$,
$f(0)= 0$,
$f(1) = -5$, and
$f(2) = 12$,
then what are the $x$-intercepts of the graph of $f$?

\(\begin{array}{|llcll|} \hline \boxed{f(x)=ax^3+bx^2+cx+d }\\\\ f(0) = 0: & 0 = a\cdot0^3+b\cdot 0^2+c\cdot 0 + d \\ & \mathbf{\boxed{d=0}} \\\\ \boxed{f(x)=ax^3+bx^2+cx+0 \\ f(x) = x(ax^2+bx+c) }\\\\ f(-1) = 15: & 15 = (-1)\left(a(-1)^2+b(-1)+c \right) \\ & 15 = (-1) (a-b+c ) \\ &\mathbf{ 15 = -a+b-c \qquad (1) } \\ f(1) = -5: & -5 = 1\cdot\left(a(1)^2+b(1)+c \right) \\ &\mathbf{ -5 = a+b+c \qquad (2) }\\\\ (1)+(2): & 15-5 =b+b \\ & 10 = 2b \\ & \mathbf{\boxed{b=5}} \\\\ \text{see }(1): & 15 = -a+b-c \quad b=5 \\ & 15 = -a+5-c \\ & 10 = -a-c \\ & \mathbf{c = -10-a \qquad (3)} \\\\ \boxed{f(x) = x(ax^2+bx+c) \\ f(x)=x(ax^2+5x-10-a)} \\\\ f(2) = 12: & 12 = 2\cdot(a\cdot2^2+5\cdot 2-10-a ) \\ & 6 = 4a-a \\ & 6 = 3a \\ & \mathbf{\boxed{a=2}} \\\\ \text{see }(3): & c = -10-a \quad a=2 \\ & c = -10-2 \\ & \mathbf{\boxed{c=-12}} \\ \hline \end{array}\)

\(\text{The polynomial $f(x)$ of degree $3$ is:} \\ \boxed{f(x) = 2x^3 + 5x^2-12x \\ f(x) = x(2x^2+5x-12) }\)

\(\text{x-intercepts $f(x) = 0\ ?$}\\ \begin{array}{|rcll|} \hline \boxed{ f(x) = x(2x^2+5x-12) }\\\\ 0 &=& x(2x^2+5x-12) \\ \mathbf{x_1} &\mathbf{=}&\mathbf{ 0} \\\\ 2x^2+5x-12 &=& 0 \\ x &=& \dfrac{-5\pm \sqrt{25-4\cdot 2\cdot (-12) } }{2\cdot 2} \\ x &=& \dfrac{-5\pm \sqrt{25+96 } }{4} \\ x &=& \dfrac{-5\pm \sqrt{121} }{4} \\ x &=& \dfrac{-5\pm 11 }{4} \\\\ x_2 &=& \dfrac{-5+ 11 }{4} \\ x_2 &=& \dfrac{6}{4} \\ \mathbf{x_2} & \mathbf{=}& \mathbf{ 1.5 } \\\\ x_3 &=& \dfrac{-5- 11 }{4} \\ x_3 &=& -\dfrac{16}{4} \\ \mathbf{x_3} & \mathbf{=}& \mathbf{ -4 } \\ \hline \end{array} \)

The x-intrcepts are: \( x=-4,\ x=0,\ x=1.5\)

The graph:

If f(x)=x^5-1/3, find f^-1(-31/96).

\(\begin{array}{|rcll|} \hline \boxed{f\left(f^{-1}\left(\dfrac{-31}{96}\right)\right) = \dfrac{-31}{96} \qquad (1) } \\\\ f(x) &=& x^5-\dfrac{1}{3} \quad | \quad x = f^{-1}\left(\dfrac{-31}{96}\right) \\\\ f\Big(f^{-1}\left(\dfrac{-31}{96}\right)\Big) &=& \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5-\dfrac{1}{3} \\\\ && \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5-\dfrac{1}{3} = \dfrac{-31}{96} \quad | \quad \text{ see } (1) \\\\ && \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5 = \dfrac{1}{3} - \dfrac{31}{96} \\\\ && \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5 = \dfrac{96-3\cdot 31}{3\cdot 96} \\\\ && \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5 = \dfrac{3}{3\cdot 96} \\\\ && \left(f^{-1}\left(\dfrac{-31}{96}\right) \right)^5 = \dfrac{1}{96} \\\\ && f^{-1}\left(\dfrac{-31}{96}\right) = \sqrt[5]{\dfrac{1}{96}} \\\\ && f^{-1}\left(\dfrac{-31}{96}\right) = \sqrt[5]{0.01041666667} \\\\ && \mathbf{ f^{-1}\left(\dfrac{-31}{96}\right) = 0.40137078088 } \\ \hline \end{array}\)

Find 2^{-1} mod{185}, as a residue modulo 185. (Give an answer between 0 and 184, inclusive.)

\(\begin{array}{rcll} \text{Let} \\ & 2\cdot 2^{-1} \equiv 1 \pmod{185} \\ \end{array} \)

\(\begin{array}{rcll} \text{Let} \\ & 2\cdot 92 = 184 \equiv -1 \pmod {185} \\ \end{array} \)

\(\begin{array}{llcll} \text{square this equation: } \\ & (2\cdot 92)(2\cdot 92) &\equiv& (-1)(-1) \pmod{185} \\ & (2) (92^2\cdot 2) &\equiv& 1 \pmod{185} \\ & (2) (16928) &\equiv& 1 \pmod{185} \quad | \quad 16928 \equiv 93 \pmod{185} \\ & (2)\underbrace{(93)}_{=(2)^{-1}} &\equiv& 1 \pmod{185} \\ \end{array}\)

\(\text{So $2^{-1}=\boxed{93}$ is the multiplicative inverse to $2$ modulo $185$}.\)

Let A=111111 and B=142857. Find a positive integer N with six or fewer digits such that 

N is the multiplicative inverse of AB modulo 1,000,000.

\(\begin{array}{rcll} \text{Let} \\ & A=111111 \\ \text{and} \\ & B=142857 \\ \end{array}\)

\(\begin{array}{rcll} A\text{ and } B \text{ are factors of } 999999. \\ & 9A=999999 \\ \text{and} \\ & 7B=999999 \\ \end{array}\)

\(\begin{array}{rcll} A\text{ and } B \text{ modulo } 1000000. \\ & 9A \equiv -1 \pmod{1000000} \\ \text{and} \\ & 7B \equiv -1 \pmod{1000000} \\ \end{array}\)

\(\begin{array}{rcll} \text{Multiply these equations: } \\ & (9A)(7B) &\equiv& (-1)(-1) \pmod{1000000} \\ & (AB) (9\cdot 7) &\equiv& 1 \pmod{1000000} \\ & (AB)\underbrace{(63)}_{=(AB)^{-1}} &\equiv& 1 \pmod{1000000} \\ \end{array}\)

\(\text{So $N=\boxed{63}$ is the multiplicative inverse to $AB$ modulo $1000000$.} \)

If f(x)=x^5-1/1, find f^-1(-31/96).

If the permutations of the first 5 letters, a, b, c, d, e,

are arranged in alphabetical order from the beginning to the end,

then what is the alphabetical order of the 77th term? How about the 100th term?

sorted...

\(\begin{array}{|rcll|} \hline 1.& abcde \\ 2.& abced \\ 3.& abdce \\ 4.& abdec \\ 5.& abecd \\ 6.& abedc \\ 7.& acbde \\ 8.& acbed \\ 9.& acdbe \\ 10.& acdeb \\ 11.& acebd \\ 12.& acedb \\ 13.& adbce \\ 14.& adbec \\ 15.& adcbe \\ 16.& adceb \\ 17.& adebc \\ 18.& adecb \\ 19.& aebcd \\ 20.& aebdc \\ 21.& aecbd \\ 22.& aecdb \\ 23.& aedbc \\ 24.& aedcb \\ 25.& bacde \\ 26.& baced \\ 27.& badce \\ 28.& badec \\ 29.& baecd \\ 30.& baedc \\ \hline \end{array} \begin{array}{|rcll|} \hline 31.& bcade \\ 32.& bcaed \\ 33.& bcdae \\ 34.& bcdea \\ 35.& bcead \\ 36.& bceda \\ 37.& bdace \\ 38.& bdaec \\ 39.& bdcae \\ 40.& bdcea \\ 41.& bdeac \\ 42.& bdeca \\ 43.& beacd \\ 44.& beadc \\ 45.& becad \\ 46.& becda \\ 47.& bedac \\ 48.& bedca \\ 49.& cabde \\ 50.& cabed \\ 51.& cadbe \\ 52.& cadeb \\ 53.& caebd \\ 54.& caedb \\ 55.& cbade \\ 56.& cbaed \\ 57.& cbdae \\ 58.& cbdea \\ 59.& cbead \\ 60.& cbeda \\ \hline \end{array} \begin{array}{|rcll|} \hline 61.& cdabe \\ 62.& cdaeb \\ 63.& cdbae \\ 64.& cdbea \\ 65.& cdeab \\ 66.& cdeba \\ 67.& ceabd \\ 68.& ceadb \\ 69.& cebad \\ 70.& cebda \\ 71.& cedab \\ 72.& cedba \\ 73.& dabce \\ 74.& dabec \\ 75.& dacbe \\ 76.& daceb \\ \color{red}77.& \huge{\color{red}daebc} \\ 78.& daecb \\ 79.& dbace \\ 80.& dbaec \\ 81.& dbcae \\ 82.& dbcea \\ 83.& dbeac \\ 84.& dbeca \\ 85.& dcabe \\ 86.& dcaeb \\ 87.& dcbae \\ 88.& dcbea \\ 89.& dceab \\ 90.& dceba \\ \hline \end{array} \begin{array}{|rcll|} \hline 91.& deabc \\ 92.& deacb \\ 93.& debac \\ 94.& debca \\ 95.& decab \\ 96.& decba \\ 97.& eabcd \\ 98.& eabdc \\ 99.& eacbd \\ \color{red}100.& \huge{\color{red}eacdb } \\ 101.& eadbc \\ 102.& eadcb \\ 103.& ebacd \\ 104.& ebadc \\ 105.& ebcad \\ 106.& ebcda \\ 107.& ebdac \\ 108.& ebdca \\ 109.& ecabd \\ 110.& ecadb \\ 111.& ecbad \\ 112.& ecbda \\ 113.& ecdab \\ 114.& ecdba \\ 115.& edabc \\ 116.& edacb \\ 117.& edbac \\ 118.& edbca \\ 119.& edcab \\ 120.& edcba \\ \hline \end{array} % % // ======================================================================= \begin{array}{|rcll|} \hline \hline \end{array} % % // ======================================================================= \begin{array}{|rcll|} \hline \hline \end{array} % % // ======================================================================= \begin{array}{|rcll|} \hline \hline \end{array}\)

There are four positive integers a,b,c,d less than 8 which are invertible modulo 8.

Find the remainder when (abc+abd+acd+bcd)(abcd)^{-1} is divided by 8.

\(\begin{array}{|rcll|} \hline && (abc+abd+acd+bcd)(abcd)^{-1} \\ &=& \dfrac{abc}{abcd} +\dfrac{abd}{abcd}+\dfrac{acd}{abcd}+\dfrac{bcd}{abcd} \\ &=& \dfrac{1}{d} +\dfrac{1}{c}+\dfrac{1}{b}+\dfrac{1}{a} \\ &=& a^{-1}+b^{-1}+c^{-1}+d^{-1} \\ \hline \end{array} \)

\(\begin{array}{|lrcl|} \hline \gcd(1,8)=\gcd(3,8)=\gcd(5,8)=\gcd(7,8)=1 \quad & | \quad a=1\quad b=3\quad c=3\quad d=5 \\\\ \begin{array}{|rcl|} \hline \phi(8)&=& 8\cdot\left(1-\dfrac12 \right) \\ &=& 4 \\ \hline \end{array} \\ \hline \end{array}\)

\(\small{ \begin{array}{|rcll|} \hline && \Big( 1^{-1} \pmod {8} + 3^{-1} \pmod {8} + 5^{-1} \pmod {8} + 7^{-1}\pmod {8} \Big)\pmod {8} \\\\ &=& \Big( 1^{\phi(8)-1} \pmod {8}+ 3^{\phi(8)-1} \pmod {8} + 5^{\phi(8)-1} \pmod {8} + 7^{\phi(8)-1}\pmod {8} \Big) \pmod {8} \\\\ &=& \Big( 1^{4-1} \pmod {8}+ 3^{4-1} \pmod {8} + 5^{4-1} \pmod {8} + 7^{4-1}\pmod {8} \Big) \pmod {8} \\\\ &=& \Big( 1^{3} \pmod {8}+ 3^{3} \pmod {8} + 5^{3} \pmod {8} + 7^{3}\pmod {8} \Big) \pmod {8} \\\\ &=& ( 1^{3}+ 3^{3} + 5^{3} + 7^{3} ) \pmod {8} \\\\ &=& ( 1+ 27 + 125 + 343 ) \pmod {8} \\\\ &=& 496 \pmod {8} \\\\ &=& 62\cdot 8 \pmod {8} \\\\ &\mathbf{=}&\mathbf{ 0 \pmod {8} } \\ \hline \end{array} }\)

What is the residue modulo 16 of the sum of the modulo 16 inverses of the first 8 positive odd integers?

Express your answer as an integer from 0 to 15, inclusive.

\(\begin{array}{|lrcl|} \hline \gcd(1,16)=\gcd(3,16)=\gcd(5,16)=\gcd(7,16) \\ =\gcd(9,16)=\gcd(11,16)=\gcd(13,16)=\gcd(15,16)=1 \\\\ \begin{array}{|rcl|} \hline \phi(16)&=& 16\cdot\left(1-\dfrac12 \right) \\ &=& 8 \\ \hline \end{array} \\ \hline \end{array} \)

\(\begin{array}{|rcll|} \hline && \Big( 1^{-1} \pmod {16} + 3^{-1} \pmod {16} + 5^{-1} \pmod {16} \\ && + 7^{-1} \pmod {16} + 9^{-1} \pmod {16} + 11^{-1} \pmod {16} \\ && + 13^{-1} \pmod {16} + 15^{-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{\phi(16)-1} \pmod {16} + 3^{\phi(16)-1} \pmod {16} + 5^{\phi(16)-1} \pmod {16} \\ && + 7^{\phi(16)-1} \pmod {16} + 9^{\phi(16)-1} \pmod {16} + 11^{\phi(16)-1} \pmod {16} \\ && + 13^{\phi(16)-1} \pmod {16} + 15^{\phi(16)-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{8-1} \pmod {16} + 3^{8-1} \pmod {16} + 5^{8-1} \pmod {16} \\ && + 7^{8-1} \pmod {16} + 9^{8-1} \pmod {16} + 11^{8-1} \pmod {16} \\ && + 13^{8-1} \pmod {16} + 15^{8-1} \pmod {16} \Big) \pmod {16} \\\\ &=& \Big( 1^{7} \pmod {16} + 3^{7} \pmod {16} + 5^{7} \pmod {16} \\ && + 7^{7} \pmod {16} + 9^{7} \pmod {16} + 11^{7} \pmod {16} \\ && + 13^{7} \pmod {16} + 15^{7} \pmod {16} \Big) \pmod {16} \\\\ &=& ( 1^{7}+ 3^{7} + 5^{7} + 7^{7} + 9^{7}+ 11^{7} + 13^{7}+ 15^{7} ) \pmod {16} \\\\ &=& ( 1+ 2187 + 78125 + 823543 + 4782969 \\ && + 19487171 + 62748517+ 170859375 ) \pmod {16} \\\\ &=& 258781888 \pmod {16} \\\\ &=& 16173868\cdot 16 \pmod {16} \\\\ &\mathbf{=}&\mathbf{ 0 \pmod {16} } \\ \hline \end{array}\)