Monday, 3 March 2014

elementary number theory - How to find the inverse modulo m?



For example:
$$7x \equiv 1 \pmod{31} $$
In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do?



Update
If I have a general modulo equation:
$$5x + 1 \equiv 2 \pmod{6}$$



What is the fastest way to solve it? My initial thought was:

$$5x + 1 \equiv 2 \pmod{6}$$
$$\Leftrightarrow 5x + 1 - 1\equiv 2 - 1 \pmod{6}$$
$$\Leftrightarrow 5x \equiv 1 \pmod{6}$$



Then solve for the inverse of $5$ modulo 6. Is it a right approach?



Thanks,


Answer




  1. One method is simply the Euclidean algorithm:

    \begin{align*}
    31 &= 4(7) + 3\\\
    7 &= 2(3) + 1.
    \end{align*}

    So $ 1 = 7 - 2(3) = 7 - 2(31 - 4(7)) = 9(7) - 2(31)$. Viewing the equation $1 = 9(7) -2(31)$ modulo $31$ gives $ 1 \equiv 9(7)\pmod{31}$, so the multiplicative inverse of $7$ modulo $31$ is $9$. This works in any situation where you want to find the multiplicative inverse of $a$ modulo $m$, provided of course that such a thing exists (i.e., $\gcd(a,m) = 1$). The Euclidean Algorithm gives you a constructive way of finding $r$ and $s$ such that $ar+ms = \gcd(a,m)$, but if you manage to find $r$ and $s$ some other way, that will do it too. As soon as you have $ar+ms=1$, that means that $r$ is the modular inverse of $a$ modulo $m$, since the equation immediately yields $ar\equiv 1 \pmod{m}$.


  2. Another method is to play with fractions Gauss's method:
    $$\frac{1}{7} = \frac{1\times 5}{7\times 5} = \frac{5}{35} = \frac{5}{4} = \frac{5\times 8}{4\times 8} = \frac{40}{32} = \frac{9}{1}.$$
    Here, you reduce modulo $31$ where appropriate, and the only thing to be careful of is that you should only multiply and divide by things relatively prime to the modulus. Here, since $31$ is prime, this is easy. At each step, I just multiplied by the smallest number that would yield a reduction; so first I multiplied by $5$ because that's the smallest multiple of $7$ that is larger than $32$, and later I multiplied by $8$ because it was the smallest multiple of $4$ that is larger than $32$. Added: As Bill notes, the method may fail for composite moduli.





Both of the above methods work for general modulus, not just for a prime modulus (though Method 2 may fail in that situation); of course, you can only find multiplicative inverses if the number is relatively prime to the modulus.



Update. Yes, your method for general linear congruences is the standard one. We have a very straightforward method for solving congruences of the form $$ax \equiv b\pmod{m},$$
namely, it has solutions if and only if $\gcd(a,m)|b$, in which case it has exactly $\gcd(a,m)$ solutions modulo $m$.



To solve such equations, you first consider the case with $\gcd(a,m)=1$, in which case $ax\equiv b\pmod{m}$ is solved either by finding the multiplicative inverse of $a$ modulo $m$, or as I did in method $2$ above looking at $\frac{b}{a}$.



Once you know how to solve them in the case where $\gcd(a,m)=1$, you can take the general case of $\gcd(a,m) = d$, and from
$$ax\equiv b\pmod{m}$$
go to

$$\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},$$
to get the unique solution $\mathbf{x}_0$. Once you have that unique solution, you get all solutions to the original congruence by considering
$$\mathbf{x}_0,\quad \mathbf{x}_0 + \frac{m}{d},\quad \mathbf{x}_0 + \frac{2m}{d},\quad\ldots, \mathbf{x}_0 + \frac{(d-1)m}{d}.$$


elementary number theory - Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction.



For example: 1/2 mod 3.



When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?

real analysis - Unsure of my work evaluating $int frac{dx}{sqrt{x + sqrt{x + sqrt{x + cdots}}}}$



This Question is an Extension of this Previously Asked Question: Nested root integral $\int_0^1 \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x}}}}$



I was looking into answering the question of whether it was possible to integrate the fully nested root integral of the variety described in the previous problem:
$$
\int \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}}
$$

So I started by defining the nested root in another way

$$
u=\sqrt{x+u} \therefore
\\
u^2-u=x
\\
(2u-1)du = dx
$$

Using the results of the substitution I have set up
$$
\int \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}} = \int \frac{2u-1}{u} du

\\
= \int \left(2-\frac{1}{u}\right)du = 2u-\ln(u)
$$



I am unsure of my work, as I have never attempted to integrate any infinitely nested functions. Therefore I have no idea whether my method for u-substitution is valid. Am I just living under a rock or have other people seen this method used previously? For such a seemingly intimidating problem it was surely quite easy.



I had difficulty checking my work using wolfram alpha, but I managed to confirm that this works for the definite integral limits from $x = 1$ to $x = 2$ and from $x = 1$ to $x = 3$. Maybe I am just flat out wrong and got lucky on these two calculations?


Answer



Short Answer:




Your work is perfectly fine if your lower and upper integral limits satisfy $0 < a \leq b$. In that case your answer $2u - \ln(u)$ even has a nice closed form purely in terms of $x$:




$$
\int_a^b \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}} = \Big[\big(1 + \sqrt{4x + 1}\big) - \ln\Big(\frac{1}{2}\big(1 + \sqrt{4x + 1}\big)\Big)\Big]_a^b
$$




This formula also continues to work for a lower limit of $a = 0$ if you interpret either the integral and/or the nested radical $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ in the denominator properly enough.




Long Answer (Analysis):



Since you used $u$-substitution, your method should work as long as the conditions for an integration by substitution are met. Say you are integrating over some interval $[a, b]$. You have to verify:




  • Does the function $u(x) = \sqrt{x + u(x)}$ that you defined implicitly actually make sense over $[a, b]$? In other words, is there really a function $u : [a, b] \to \Bbb R$ that satisfies that recursion?


  • Is the function $u(x)$ actually differentiable over $[a, b]$?




$\underline{\textit{There is some good news for these questions:}}$




As long as $x > 0$, there is a well-defined expression for $u$ in terms of $x$ when $u = \sqrt{x + u}$. To realize this, we need translate the intuitive expression $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ into the precise language of calculus. Only then can we bring the full power of calculus to bear on this problem. So formally what is going on with a nested radical like $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ is this:




Let $u_{x,1} = \sqrt{x}$ and define recursively the sequence $u_{x,n + 1} = \sqrt{x + u_{x,n}}$ ($n \in \Bbb Z_+$). If $$u_x = \lim\limits_{n \to \infty}u_{x,n}$$ exists, then we may define our sought-after function $u$ at $x$ to be $u(x) = u_x$. In essence, the limit $\lim\limits_{n \to \infty}u_{x,n}$ is mathematically what we define the expression $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ to be. And we can easily check that $u_x = \sqrt{x + u_x}$ by taking the limit as $n \to \infty$ at both sides of the equation $u_{x,n + 1} = \sqrt{x + u_{x,n}}$.




Now the good news is that, as long as $x > 0$, you can show that the sequence $u_{x,n}$ is bounded and monotonically increasing so that it does converge to a definite limit, namely



$$u_x = \frac{1}{2}\big(1 + \sqrt{4x + 1}\big)$$




Hence, our function $u(x) = u_x$ is well-defined for $x > 0$. Also, note that the formula above should not surprise you. You can easily see where it originated:



Informally, if you take your substitution equation $u^2 - u = x$ and wrote it as a quadratic equation $u^2 - u - x = 0$, you can solve it by thinking of $x$ as a constant. And indeed, one of the solutions that pops out is precisely $u_+ = \frac{1}{2}\big(1 + \sqrt{4x + 1}\big)$. You can eliminate the other solution $u_- = \frac{1}{2}\big(1 - \sqrt{4x + 1}\big)$ since it is negative if $x > 0$ and by convention square roots are positive.




So as long as $x > 0$, you can safely take $$u(x) = \frac{1}{2}\big(1 + \sqrt{4x + 1}\big)$$ as the $u$-substitution function which satisfies $u = \sqrt{x + u}$. In fact, as is apparent from the formula, $u(x)$ is even differentiable in this case.




$\underline{\textit{But there are caveats:}}$




$1.\ \textbf{Note that for $x < 0$, the limit does not make sense:}$ as the very first sequence element $u_{x,1} = \sqrt{x}$ is not real. So, from this very analysis, you can immediately conclude that you should not be integrating over negative values in your integral.



$2.\ \textbf{Next, at $x = 0$, things almost work out but break down anyway:}$ Note, we only managed to eliminate $\frac{1}{2}\big(1 - \sqrt{4x + 1}\big)$ as a candidate for the limit above because it was negative if $x > 0$. Well, if $x = 0$, then $u_- = \frac{1}{2}\big(1 - \sqrt{4x + 1}\big) = 0$ and you can no longer eliminate it that easily. So, we must go back to our definition of $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ in terms of sequences to arbitrate between $u_+$ and $u_-$. Applying that definition when $x = 0$, we see that $u_- = 0$ is the candidate that is chosen this time not $u_+ = 1$. This is because in this case, all the sequence elements $u_{x,n}$ are zero: $$u_{x=0,1} = \sqrt{x} = \sqrt{0} = 0,\quad u_{x=0,2} = \sqrt{x + u_{x=0,1}} = \sqrt{0 + 0} = 0,\quad \ldots \text{ etc}$$



Hence, $\lim\limits_{n \to \infty}u_{x=0,n} = 0$ and $u(0) = 0$. However, approaching $0$ from the right, we see that
$$\lim\limits_{x \to 0+}u(x) = \frac{1}{2}\big(1 + \sqrt{4\cdot0 + 1}\big) = 1$$ And therefore even though $u(x)$ is defined at $x = 0$, it is sadly not continuous there, let alone differentiable. So the $u$-substitution Theorem no longer applies.



In any case, there is an even worse problem when $x = 0$. Note that the function you are trying to integrate $f(x) = \sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ is undefined at $x = 0$ because as we saw, our definition of $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ in terms of sequences gives you a $0$ when $x = 0$. So there would be a $0$ in your denominator for $f(x)$ if that was allowed.




$\underline{\textit{Okay, so we have concluded so far that:}}$



As long as your integration interval $[a, b]$ satisfies $0 < a \leq b$, your work should go through and you can use $u(x) = \frac{1}{2}\big(1 + \sqrt{4x + 1}\big)$ as the explicit formula for $u$ to express your final integral answer:




$$
\int_a^b \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}} = \Big[\big(1 + \sqrt{4x + 1}\big) - \ln\Big(\frac{1}{2}\big(1 + \sqrt{4x + 1}\big)\Big)\Big]_a^b
$$





$\underline{\textit{Fixing the breakdown at $x = 0$:}}$



If you really want $x = 0$ as one of the limits e.g.
$$
\int_0^b \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}}
$$
for $b > 0$, you can do so in two ways, both of which lead to the same result:




  • You can modify the definition of $\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}$ thus: it defaults to the usual definition via sequences if $x > 0$ and to $\frac{1}{2}(1 + \sqrt{4 \cdot 0 + 1}) = 1$ if $x = 0$. Then you can safely use $u(x) = \frac{1}{2}\big(1 + \sqrt{4x + 1}\big)$ for all $x \geq 0$. And the answer you will get for your integral is exactly what you would expect by plugging in $a = 0$ in the closed form I gave above:
    $$

    \big(1 + \sqrt{4b + 1}\big) - \ln\Big(\frac{1}{2}\big(1 + \sqrt{4b + 1}\big)\Big) - 2
    $$


  • On the other hand, you can instead take a limiting integral in the same spirit that we define $\int_0^b \frac{1}{x^2}dx$ to get around the singularity of $\frac{1}{x^2}$ at $0$. That is, you can define:
    \begin{align*}
    \int_0^b \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}} &:= \lim_{a \to 0+}\int_a^b \frac{dx}{\sqrt{x+\sqrt{x+\sqrt{x+\ldots}}}} \\
    &= \lim_{a \to 0+}\big[2u(x) - \ln(u(x))\big]_a^b
    \end{align*}
    This leads to the same answer because ultimately $\lim\limits_{a \to 0^+}u(x) = 1$.



real analysis - Convergence of $sumlimits_{n=1}^{infty}a_n$ implies convergence of $sumlimits_{n=1}^{infty}a_n^{sigma_n}$ where $sigma_n=frac{n}{n+1}$?

I really don't want spoilers for this problem, but I am wondering if my approach is correct. (I am of course looking for a solution based on "standard" stuff regarding series, not relying on some exotic theorem from which it may follow immediately.)




Let $ a_n > 0 $ for all $ n = 1, 2, 3, \ldots$ and suppose $ \sum\limits_{n=1}^{\infty} a_n $ converges. Let $ \sigma_n = \frac{n}{n+1} $.



To show that $ \sum\limits_{n=1}^{\infty} a_n^{\sigma_n} $ converges, first observe that



$$ \limsup\limits_{n \to \infty} ([a_n^{\sigma_n}]^{1/n}) = \limsup\limits_{n \to \infty} (a_n^{1/(n+1)}) = \limsup\limits_{n \to \infty} (a_n^{1/n}) $$



so since $ \sum a_n $ converges, $ \limsup \sqrt[n]{a_n^{\sigma_n}} \leq 1 $.



If $ \limsup (\sqrt[n]{a_n^{\sigma_n}}) < 1 $, the result follows (by the Root test). Suppose $ \limsup (\sqrt[n]{a_n^{\sigma_n}}) = 1 $ intsead. Then (this part may be totally wrong) since $ a_n > 0 $ and $ a_n \to 0 $, $ \lim\limits_{n \to \infty} \sqrt[n]{a_n^{\sigma_n}} = 1 $, which means




$$ \lim\limits_{n \to \infty} \dfrac{1}{\sqrt[n]{a_n}} = \liminf\limits_{n \to \infty} \dfrac{1}{\sqrt[n]{a_n}} = 1. $$



Hence one can find $ N \in \mathbf{N} $ such that for all $ n \geq N $, (i) $ 0 < a_n < 1 $ and (ii) $ 1 < \dfrac{1}{a_n^{1/(n+1)}} < 2 $. Then



$$ |a_n^{\sigma_n}| = \left|a_n^{1 - \tfrac{1}{n+1}}\right| = |a_n| \cdot \left|\dfrac{1}{a_n^{1/(n+1)}}\right| \leq 2|a_n| $$



so $ \sum\limits_{n=1}^{\infty} a_n^{\sigma_n} $ must converge by the Comparison test.

Sunday, 2 March 2014

sequences and series - Prove by induction that $sum_{n=1}^infty frac{1}{2^n} = 1$

The title explains the problem fairly well; is there a way to prove by induction that $\sum_{n=1}^\infty \frac{1}{2^n} = 1$. If not are there other ways?



I have thought of showing it by rewriting the series so that. $$\sum_{n=1}^\infty \frac{1}{2^n} = 1 \implies \sum_{n=1}^\infty \frac{1}{2}(\frac{1}{2})^{n-1} = 1$$



And then from there conclude that it is a geometric series with the values $r = 1/2$ and $a=1/2$ thus $$\sum_{n=1}^\infty \frac{1}{2^n} = \frac{1/2}{1-1/2} = 1$$




This seems like kind of a vodoo proof, so i was wondering if its possible to do this by induction?

calculus - How should I prove Cauchy's mean value theorem using Lagrange's mean value theorem.




I want to prove Cauchy's mean value theorem without using Rolle's theorem and only using Lagrange's mean value theorem. I tried to prove this by assuming $\frac{f'(x)}{g'(x)}$ but I proceed further please help me out with this.


Answer



If $f$ and $g$ are continuous real functions on $[a,b]$ which are differentiable on $(a,b)$. We could construct a function $F(x)=[f(b)-f(a)]g(x)-[g(b)-g(a)]f(x).$ Obviously, $F(x)$ is continuous on $[a,b]$ and differentiable on $(a,b).$ Applying Lagrange's mean value theorem to $F(x)$, we obtain a point $\epsilon \in (a,b)$ such that
$$
F(b)-F(a)=F'(\epsilon)(b-a).
$$

Noting that $F(b)-F(a)=0$, we have
$$
F'(\epsilon)=[f(b)-f(a)]g(\epsilon)-[g(b)-g(a)]f(\epsilon)=0.
$$


That is,
$$
[f(b)-f(a)]g(\epsilon)=[g(b)-g(a)]f(\epsilon).
$$


calculus - Simpler way to compute a definite integral without resorting to partial fractions?



I found the method of partial fractions very laborious to solve this definite integral :
$$\int_0^\infty \frac{\sqrt[3]{x}}{1 + x^2}\,dx$$



Is there a simpler way to do this ?


Answer




Perhaps this is simpler.



Make the substitution $\displaystyle x^{2/3} = t$. Giving us



$\displaystyle \frac{2 x^{1/3}}{3 x^{2/3}} dx = dt$, i.e $\displaystyle x^{1/3} dx = \frac{3}{2} t dt$



This gives us that the integral is



$$I = \frac{3}{2} \int_{0}^{\infty} \frac{t}{1 + t^3} \ \text{d}t$$




Now make the substitution $t = \frac{1}{z}$ to get



$$I = \frac{3}{2} \int_{0}^{\infty} \frac{1}{1 + t^3} \ \text{d}t$$



Add them up, cancel the $\displaystyle 1+t$, write the denominator ($\displaystyle t^2 - t + 1$) as $\displaystyle (t+a)^2 + b^2$ and get the answer.


real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...