Number Theory GCD Homework Problem

This is a problem from my homework:

If $a\mid bc$, show that $a\mid $gcd$(a,b)$gcd$(a,c)$.

(Hint: use Euclid's lemma: If $a_0\mid b_0c_0$, with gcd$(a_0,b_0)=1$, then $a_0\mid c_0$.)

I tried setting $a_0=a$, $c_0=c$, and $b_0=$gcd$(a,b)$, to try to find gcd$($gcd$(a,b),a)$, but I stopped here as I wasn't able to go further.

Thanks in advance!

Answer

$a_0=a,b_0=\gcd(a,b)$ does not meet the condition $\gcd(a_0,b_0)=1$

The key is that $$\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1$$

let $$a_0=\frac{a}{\gcd(a,b)},b_0=\frac{b}{\gcd(a,b)},c_0=c$$
we have $$\begin{align}a|bc\Rightarrow & a_0*\gcd(a,b)|b_0*\gcd(a,b)*c_0\\\Rightarrow & a_0|b_0c_0\end{align}$$
and $$\gcd(a_0,b_0)=1$$ Thus $$a_0|c_0 \Rightarrow \frac{a}{gcd(a,b)}|c$$

obviously $$\frac{a}{gcd(a,b)}|a$$. So $$\frac{a}{gcd(a,b)}|\gcd(a,c)$$
ie. $$a|\gcd(a,b)\gcd(a,c)$$

linear algebra - Clarification on the meaning of "uniqueness" in the (linked) Matrix diagonalization theorem

I came across this source yesterday, where they say: given a square real matrix S of size $nxn$, with n linearly independent eigenvectors, there exists an eigendecomposition such as $S=UDU^{-1}$. If the eigenvalues on the diagonal of D are distinct (which I suppose it means of mulitplicity 1, correct?), this decomposition is unique.

I don't understand the latter sentence (this decomposition is unique). What do they mean by unique?

For example, given a square matrix, in the particular case where the matrix is symmetric, if all eigenvalues have multiplicity 1, then each eigenvector associated to a certain eigenvalue can be re-expressed as a multiplication between a scalar and the normalized eigenvector for that eigenvalue. So denoting by x the normalized eigenvector, taking $cx$, where c is a scalar, still gives an eigenvector which is linearly independent from the eigenvectors of the other eigenvalues (i.e. if the multiplicity of all eigenvalues is 1, then normalized eigenvectors are unique up to a sign transformation +/-1*x, so setting c=1 implies $1x$ is clearly unique). So in that case, the decomposition $S=UDU^{-1}$ is not unique: there may exist multiple matrixes $U$ such that $S=UDU^{-1}$ obtained by multiplying any eigenvector in the columns of $U$ by a scalar. Please correct me if I am wrong.

In that source they often talk about standardized eigenvectors, so maybe are they referring to the special case where we consider only the standardized version of the eigenvectors? As specified in the theorem below in the same page regarding symmetric square matrixes? Otherwise, what am I misinterpreting?

Answer

You are right that the decomposition is not unique. And the referenced text is wrong in claiming that it is. Certainly the change of basis matrix $U$ is not unique, and its columns can be independently multiplied by nonzero scalars without changing the validity of the decomposition. The diagonal matrix has more claim to unicity, but still its entries can be permuted (if the columns of $U$ are correspondingly permuted). However the linked text take that into account be requiring the diagonal entries to be decreasing. Note that this can only be done since the text is supposing the existence of (distinct) real eigenvalues; if one wants to allow complex eigenvalues, then this method will not so easily.

elementary number theory - Prove the following: If $a mid bc$, then $a mid gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I can't prove that $a \mid bc$, if and only if $a\mid b$ and $a\mid c$. Please help. Thanks.

sequences and series - Blocks of Pyramid Pattern Expression

There is a pattern following, and trying to find the algebraic expression

Each layer (from the top).

Diagram.

So the first layer has 1, second has 4, third has 9, and the fourth has 16.

That's how the sequence is increasing.

What I'm looking for is,

When the second layer is added with the first layer,

Third layer is added with the second and first,

Fourth is added with third,second and first.

So something like this.

I am trying to find the algebraic expression for this pattern.

Any ideas??

Thank you

Answer

There is a well-known formula for the sum of the first $n$ squares, but I don't want spoil your investigation, so I will give you some hints.

First, compute some more terms of the sequence. Three or four more should do.

Multiply all the terms by six, and factor the results. Notice that all of them are multiple of $n$ and $n+1$.

sequences and series - A problem about the ratio of atoms

I'm trying to find the ratio of the number of atoms in the core of a nanoparticle, and the outermost shell with each shell containing:

$10k^2+2$ atoms

Then the total number up to the $k^{th}$ shell is (I believe)

$\sum\limits_{n=1}^{k-1}(10(k-n)^2+2)$

It's this expression I'm stuck on. I'm not 100% on what I'm allowed to do to evaluate this summation. I couldn't find much about operations on summations when I went looking.

Is this expression equivalent?

$10\bigg(\sum\limits_{n=1}^{k-1}k^2+\sum\limits_{n=1}^{k-1}n^2-\sum\limits_{n=1}^{k-1}2kn\bigg)+\sum\limits_{n=1}^{k-1}2$

If so how can I evaluate these?

Edit: Note, errors fixed thanks to Gerry's advice in his answer

Answer

Remember $(k-n)^2=k^2+n^2-2kn$, so you're missing a factor of 2. Also, the 10 doesn't multiply the +2 in the sum, so your last sum shouldn't be in the parentheses.

But you are making it a bit harder than it has to be. Do you see that $$\sum_{n=1}^{k-1}(10(k-n)^2+2)=\sum_{n=1}^{k-1}(10n^2+2)$$ On the left, as $n$ goes from $1$ to $k-1$, $k-n$ goes from $k-1$ to $1$, so the form on the right adds up the same numbers.

Now all you need is the formula for $\sum_{n=1}^{k-1}n^2$, which you can find in any number of places. .

analysis - problem in measure theory

I would a appreciate if someone could take the time to check if my solution to the following problem is correct:

From http://www.math.chalmers.se/~borell/MeasureTheory.pdf, page 64, ex.6.

Let $(X, \cal{M}, \mu)$ be a positive measure space and suppose $f$ and $g$ are non-negative measurable functions such that $$ \int_{A} fd\mu = \int_A gd\mu,\quad \text{all } A \in \cal{M}. $$

$(a).$ Prove that $f = g$ a.e. $[\mu]$ if $\mu$ is $\sigma$-finite.

$(b).$ Prove that the conclusion of Part $(a)$ may fail if $\mu$ is not $\sigma$-finite.

Consider the set where $f > g.$ Denote this set $A.$ But $A=\cup_n[A_n]$ where $$A_n=\{x:f(x)>g(x)+1/n\},$$ a strictly increasing sequence hence $\mu(A)=\lim_n \mu(A_n).$ So if $\mu(A)>0,$ there is a $N$ such that $\mu(A_N)>0$ Since $X$ is $\sigma$-finite $X=\cup_m\{X_m\}$ where $\mu(X_m)< \infty.$ If $\mu(A_N)>0$ then there must exist an $M$ s.t. $\mu(\cap{A_N,X_M})>0.$ and hence integral_intersection$\{A_N,X_M\} {f} \ge$ integral_intersection$\{A_N,X_M\} {g} + 1/N\mu(\cap\{A_N,X_M\}),$ a contradiction unless the left-hand side is infinite.

In that case consider $C_n=\{x: g(x) < n \}.$

Choose $M$ s.t. $\mu(A_M,X_M,C_M) > 0,$ now integrate over this set instead to arrive at the desired contradiction. Hence $\mu(A)=0$

The same applies to the set $B=\{x:g(x)>f(x)\}, \mu(B)=0.$

error function - The integral $int_0^∞ e^{-f(x^2)} dx$

We know that :
$$\int_0^∞ e^{-x^2} dx = \frac {\sqrt{π}}{2}$$

$$\int_0^∞ e^{-x^2-\frac {a^2}{x^2}} dx = \frac {\sqrt{π}}{2}e^{-2a}$$
Both the above results can be easily proved by integration under integration. I was wondering if it can be extended to the general integral $\int_0^∞ e^{-f(x^2)} dx$. The result is surely $\frac {\sqrt{π}}{2}F$ where $F$ is a constant function. But I am unable to relate $F$ with $f$.
Any suggestions are welcome.

Answer

Here's a little list with examples of the integrals in the form:

$$\int_0^\infty e^{-f(x^2)} dx$$

---

Gamma function related integrals:

$$\int_0^\infty e^{-x^2} dx =\Gamma \left( \frac{3}{2}\right)=\frac{1}{2} \Gamma \left( \frac{1}{2}\right)=\frac{\sqrt{\pi}}{2}$$

$$\int_0^\infty e^{-x^4} dx =\Gamma \left( \frac{5}{4}\right)$$

$$\int_0^\infty e^{-x^{2n}} dx =\Gamma \left( \frac{2n+1}{2n}\right)$$

---

Bessel function related integrals:

$$\int_0^\infty e^{-a \cosh x} dx=K_0 (a)$$

$$\int_0^\infty e^{-a (1+\frac{4}{3} x^2) \sqrt{1+\frac{1}{3} x^2}} dx=\frac{1}{\sqrt{3}}K_{1/3} (a)$$

Many more examples are possible.

---

Trivial cases:

$$\int_0^\infty e^{-\ln (1+x^2)} dx=\int_0^\infty \frac{1}{1+x^2} dx=\frac{\pi}{2}$$

$$\int_0^\infty e^{-\frac{3}{2}\ln (1+x^2)} dx=\int_0^\infty \frac{1}{(1+x^2)^{3/2}} dx=1$$

$$\int_0^\infty e^{-\ln (1+x^4)} dx=\int_0^\infty \frac{1}{1+x^4} dx=\frac{\pi}{2\sqrt{2}}$$

$$\int_0^\infty e^{-\ln (\cosh x)} dx=\int_0^\infty \frac{1}{\cosh x} dx=\frac{\pi}{2}$$

And so on.

---

What this list is intended to show is that there's no general method for finding the closed forms for such integrals. They need to be dealt with on case by case basis. Sometimes generalization is possible, sometimes not.

---

An example of such a general theorem can be seen in this answer, which allows us to make an infinite number of integrals giving the same value.