discrete mathematics - Solving $3xequiv 4pmod 7$

I'm trying to learn about linear congruences of the form ax = b(mod m). In my book, it's written that if $\gcd(a, m) = 1$ then there must exist an integer $a'$ which is an inverse of $a \pmod{m}$. I'm trying to solve this example:

$$3x \equiv 4 \pmod 7$$

First I noticed $\gcd(3, 7) = 1$.

Therefore, there must exist an integer which is the multiplicative inverse of $3 \pmod 7$.

According to Bezout's Theorem, if $\gcd(a, m) = 1$ then there are integers $s$ and $t$ such that $sa+tm=1$

where $s$ is the multiplicative inverse of $a\pmod{m}$.

Using that theorem:

$\begin{align}7 = 3\cdot2 +1\\7 - 3\cdot2 = 1 \\-2\cdot3 + 7 = 1\end{align}$

$s=-2$ in the above equation so $-2$ is the inverse of $3 \pmod{7}$.

The book says that the next step to solve $3x \equiv 4 \pmod{7}$ is to multiply $-2$ on both sides.

By doing that I get:

$\begin{align}-2\cdot3x \equiv -2\cdot4 \pmod 7\\-6x\equiv -8 \pmod 7\end{align}$

What should I do after that?

I am working on this problem for hours.

Thanks :)

Answer

$$\begin{align}
3x\equiv4\pmod{7} & (\text{Original equation})\\3x\equiv -3\pmod{7} &(\text{Replaced 4 with -3(by subtracting 7)})\\x\equiv-1\pmod{7}& (\text{Divide each side by 3})\\ x\equiv6\pmod{7} &(\text{replaced -1 with 6 (by adding 7))}
\end{align}$$

P.S.- The reason you can add or subtract $7$ is one of the properties of $\pmod{7}$. You can add or subtract multiples of $7$ to the number in front of the $mod$ without effecting the equation.

calculus - Integrals involving exponential functions and the gamma function

I'm having trouble evaluating this integral

$$\int_0^\infty {e^{-ax^2}} \,dx $$

My guess is that it would evaluate into something like

$$\int_0^\infty \frac 12e^{-s}s^{\frac 12} \ldots \,dx = \frac {\Gamma\left(\frac 12\right)}{\frac{a^{\frac 12}}{2}}$$

When you do a substitution $ \sqrt{s}= \sqrt{a}x $ so that $ s = ax^2 $. I'm having trouble convincing myself though that $ \frac {d}{ds}\sqrt{s} = \left(\ldots a^\frac 12\right) $ which would satisfy the answer that I provided.

Am I doing something wrong or is my guess wrong?

Answer

If you want to use the Gamma function the substitution is $a x^2 = t$, so “$dx = \frac{1}{2\sqrt{a}}t^{-1/2}dt$".
Then the integral appears as,
$$\frac{1}{2\sqrt{a}} \int_0^\infty dt\,t^{-1/2}e^{-t} = \frac{1}{2\sqrt{a}}\Gamma(1/2)\ .$$

That's all.

algebra precalculus - Decompose into Partial Fraction. Image Added.

I really had no idea how to write these questions out without copying and pasting them onto here, so I am sorry for that..I hope adding a picture is fine. I would appreciate any kind of help, and if you dont mind suggesting a useful website, or video that can explain these problems to me. Thank you

Proving a Vector Norm Inequality Holds

Suppose we have a vector norm defined as $v(x)$ for $x \in\Bbb{ R}^n$, show that for vectors $x,y \in \Bbb{R}^n$ the following inequality holds:

$|v(x) - v(y)| \leq v(x - y)$.

I know that if $v(x)$ is a vector norm, then one of the conditions it necessarily satisfies is:

$||x + y|| \leq ||x|| + ||y||$ for all $x,y \in R^n$.

I believe the proof of the above inequality will most likely make use of this particular property but want to be careful when specifically using it and am having trouble establishing it. So far the attempt at showing the inequality I have is:

$|v(x) - v(y)| = ||x| - |y|| \leq |x| - |y|$

I am confused whether I have properly used the inequality property of vector norms and have trouble showing the original inequality, specifically how to get to the RHS of inequality. Any insight or help would be much appreciated, thanks.

Answer

You can use the triangle inequality as follows:
$$
\begin{align}
v(x) = v(y + (x-y)) \leq v(y) + v(x-y) \implies v(x)-v(y)\leq v(x-y)\tag1\\
v(y) = v(x + (y-x)) \leq v(x) + v(y-x) \implies v(y)-v(x)\leq v(y-x)\tag2

\end{align}
$$
thus
$$
\begin{align}
v(x)-v(y)\leq v(x-y)\tag1\\
-(v(x)-v(y))\leq v(x-y)\tag2
\end{align}
$$

using (1) and (2) $|v(x)-v(y)|\leq v(x-y)$.

calculus - Showing if $lim_{ntoinfty} a_n=L$ then $lim_{ntoinfty} -2a_n=-2L$ using definition

If $\displaystyle \lim_{n\to\infty} a_n=L$ then prove using the limit definition that: $\displaystyle \lim_{n\to\infty} -2a_n=-2L$.

From the given and the definition we know that: $L-\epsilon-2a_n>-2L-2\epsilon\Rightarrow |-2a_n+2L|<2\epsilon$ which concludes that: $\displaystyle \lim_{n\to\infty} -2a_n=-2L$.

I feel like I was cheating by doing that multiplication by $-2$, is it alright? it's still true for $2\epsilon$ right?

Answer

The general idea of you solution is very much correct. The only thing that is missing is that we have: $L-\epsilonfor sufficiently large $n$.

linear algebra - Let $A,B$ be $m times n$ and $n times m$ matrices, respectively. Prove that if $m > n$, $AB$ is not invertible

We haven't done anything about rank or dimensions or linear dependence / basis or determinants. Possible related facts :

1. A matrix is invertible iff it is bijective as a linear transformation.





2. An invertible matrix is row-equivalent to the identity matrix.




3. A matrix has a right inverse iff it has a left inverse.

Also, invertability is only defined for square matrices.

Answer

Since $A$ is an $m\times n$ matrix and $B$ is an $n\times m$ matrix, the product $AB$ is an $m\times m$ matrix. Suppose $m>n$ then the operator associated to left multiplication by $B$ is not injective because there are more columns than rows, so the kernel is always nontrivial (i.e. there are more column vectors than there are entries in those column vectors, so they must be linearly dependent). Said another way: the linear operator $T:\Bbb R^m\to\Bbb R^n$ with $T(v)=Bv$ is not injective because $m>n$, so the domain has higher dimension than the codomain. So there exists vectors $v,w\in\Bbb R^m$ such that $Bv=Bw$ but $v\neq w$.

Spoiler:

Thus, $$Bv=Bw\implies A(Bv)=A(Bw)\implies (AB)v=(AB)w$$ but $v\neq w$. Hence, the operator associated with left multiplication by $AB$ is not injective.

trigonometry - How to calculate a "rational" sine/cosine to specific digits of precision?

I have a toy calculator I've been tasked to create for a class project. That's great - I have most of the normal calculator stuff done (order of operations, variables, precision settings, predefined functions). The issue is that, since I'm using rational arithmetic, there's no sin/cos function built-in, so I'll have to make my own.

And the issue with that is that sines are usually irrational, so I'll have to limit it to some precision or it'll run forever. I've successfully implemented the sine Maclaurin series in code. For reference, the relevant equation from the Wikipedia article is this:

$$\sin x = \sum_{n=0}^{\infty}{\frac{(-1)^n}{(2n + 1)!}x^{2n+1}} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \frac{x^9}{9!} - \cdots$$

My program runs only until this condition is true:

$$\frac{x^i}{i!}<\frac{1}{10^p}$$

where $i = 2n + 1$ and $p$ is the desired precision in digits, but it gets very slow quite quickly (at least using a C++ interpreter, but I want it to run quickly there before I make it faster by compiling). There are some optimizations such as keeping the last numerator/denominator, but it's still not that fast.

Calculating the sine of $5\pi$ to 15 digits of precision (bad example, but it's to prove a point) using my program took 5 seconds across 34 iterations, since many later iterations end up multiplying integers greater than $1 \times 10^{900}$. $\pi$ has to be represented as a fraction, so there were very large integers involved.

I'm not sure where to ask for a better algorithm but here (or Stack Overflow, from which I've been banned for over a year, so that's not going to happen...). Even though I'm using rational arithmetic, I'm wondering if there's a more computationally efficient way to approximate a $\sin$ and $\cos$ to some amount of digits of precision. I know this isn't a programming site, but surely someone can help with the algorithm side? (preferably explained in plain English)

Note: I could offload the work onto some arbitrary-precision floating point library and then convert that back to a "rational", but that seems like cheating to me... it'll be more of a last resort.