About the LCM by GCD product

Let $a$ e $b$ be two non zero natural numbers; it is known that their product equals their GCD by LCM product, that is:

$a \cdot b = LCM(a,b) \cdot GCD(n,m)$ (1)

This formula is very useful in informatics since easy algorithms exist to calculate GCD: LCM between two numbers can therefore be calculated by calculating GCD and then applying (1).

Equation (1) can be proved in many ways; proofs can be easily found on the web (here are a couple of proofs from me, for example).

A less known more general form of the (1) is the following. Let a1,…,aN be non zero natural numbers; it’s true that:

$\prod_{i=1}^{N}a_{i} = LCM(a_{1},…,a_{N})\cdot GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a^{i}, \cdot …, \cdot \frac{1}{a_{N}}\prod_{i=1}^{N}a^{i})$ (2)

which turns out to be the (1), when we put $N=2$.

Here’s a proof of (2), which is simple provided that we calculate GCD in a way which is slightly different from traditional one (obviously equivalent).

Let $a_{1},…,a_{N}$ be N non zero natural numbers; each of them can be factorized in primes number in a unique way, some of the factors could be shared among two or more than two natural numbers, some other could appear in one of the numbers factorization only (the latters are usually referred as “not shared” factors). Let now $F = f_{1},…,f_{K}$ be the set of all the prime factors appearing in all $a_{1},…,a_{N}$ factorizations. Both shared and unique factors belong to $F$. Each of the $a_{1},…,a_{N}$ factorizes as follows:

$a_{i} = \prod_{j=1}^{K}f_{j}^{e_{ij}}, i = 1, …, N$ (3)

where some of the exponents can be zero (if that specific factor does not appear in some of the $a_{i}$ factorizations). From (3), GCD and LCM can easily be defined as follows:

$LCM(a_{1}, …, a_{N}) = \prod_{j=1}^{K}f_{j}^{\max_{i=1,…,N}(e_{ij})}$ (4)

$GCD(a_{1}, …, a_{N}) = \prod_{j=1}^{K}f_{j}^{min_{i=1,…,N}(e_{ij})}$ (5)

It’s worthwhile to notice that, if any of the $f_{j}$ did not appear in all $a_{i}$ factorizations, its minimum exponent would be 0 (zero); therefore that factor would not appear in the GCD factorization, as expected (indeed using the traditional algorithm we would consider only those factors which appear in all $a_{i}$ factorizations).

Using (4) and (5) to prove (1) is trivial. Let’s focus on the proof of (2).

First, let’s calculate the GCD at right side of (2) by using (5), that is:

$GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a_{i}, …, \frac{1}{a_{N}}\prod_{i=1}^{N}a_{i})$ (6)

In other words, we’re trying to evaluate GCD of N numbers, each of them being the product of N-1 elements among $a_{i}$. The m-th of these numbers can be factorized as follows:

$\frac{1}{a_{m}}\prod_{i=1}^{N}a^{i} = \prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-e_{mj}}$ (7)

As to calculate GCD the minimum exponent must be selected, from (7) it follows that the GCD factorization j-th factor’s $f_{j}$ exponent will be $\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})$. Hence:

$GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a_{i}, …, \frac{1}{a_{N}}\prod_{i=1}^{N}a_{i})=\prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})}$ (8)

Finally, applying powers properties at the left side of (2) and putting (4) and (8) at right side of (2), we get:

$\prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}}=\prod_{j=1}^{K}f_{j}^{\max_{i=1,…,N}(e_{ij})} \cdot \prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})}$ (9)

which is obviously true.

A powerful symmetry formula for definite integrals calculation

Let $f(x)$ be an even function, integrable in $\left [ 0,\alpha \right ]$ and $g(x)$ another function such that $g(-x)=\frac{1}{g(x)}$, $g(x)\neq0$, $g(x)\neq-1$ in $\left [ -\alpha,\alpha \right ]$.

It can be proved that:

$$\int_{-\alpha }^{\alpha }\frac{f(x)}{1+g(x)}dx=\int_{0}^{\alpha}f(x)dx (1)$$

It turns out to be an interesting formula in the sense that it allows to simplify and speed up some integrals calculations.

Let’s see some examples.

1. Let $f(x)=x^2$ and $g(x)=e^x$. In this case (1) becomes $$\int_{-1}^{1}\frac{x^2}{1+e^x}dx=\int_{0}^{1}x^2dx=\left [ \frac{1}{3}x^3 \right ]_{0}^{1}=\frac{1}{3}$$

Fig.1 – Example 1: red area is equivalent to blue area (both are $1/3$)

2. Let now $f(x)=x^2+cosx$ and $g(x)=e^{xcosx}$. We have$$\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\frac{x^2+cosx}{1+e^{xcosx}}dx=\int_{0}^{\pi/2}(x^2+cosx)dx=\left [ \frac{1}{3}x^3 +sinx\right ]_{0}^{\pi/2}=\frac{\pi}{24}+1$$

Fig. 2 – Example 2: red area is equivalent to blue area (both are $\pi/24 + 1$)

3. Finally, let $f(x)=x^2$ and $g(x)=(1+x^2)^x$. Formula (1) becomes$$\int_{-1}^{1}\frac{x^2}{1+(1+x^2)^{x}}dx=\int_{0}^{1}x^2dx=\left [ \frac{1}{3}x^3\right ]_{0}^{1}=\frac{1}{3}$$

Fig.2 – Example 3: red area is equivalent to blue area (both are $1/3$)

Proof

It’s a straightforward calculation.

$$\int_{-\alpha }^{\alpha }\frac{f(x)}{1+g(x)}dx=\int_{-\alpha }^{0}\frac{f(x)}{1+g(x)}dx+\int_{0}^{\alpha }\frac{f(x)}{1+g(x)}dx=$$

$$=\int_{-\alpha }^{0}\frac{f(x)\frac{1}{g(x)}}{1+\frac{1}{g(x)}}dx+\int_{0}^{\alpha}\frac{f(x)}{1+g(x)}dx=\int_{-\alpha }^{0}\frac{f(x)(\frac{1}{g(x)}+1-1)}{1+\frac{1}{g(x)}}dx+\int_{0}^{\alpha}\frac{f(x)}{1+g(x)}dx=$$

$$=\int_{-\alpha }^{0}\left [f(x)-\frac{f(x)}{1+\frac{1}{g(x)}} \right ]dx+\int_{0}^{\alpha}\frac{f(x)}{1+g(x)}dx=\int_{-\alpha }^{0}f(x)dx-\int_{-\alpha }^{0}\frac{f(x)}{1+\frac{1}{g(x)}}dx+\int_{0}^{\alpha}\frac{f(x)}{1+g(x)}dx=$$

applying the variable change $t=-x$ ($dt=-dx$) in the second integral and using the fact that $f(x)$ is even in the first integral,

$$=\int_{0}^{\alpha}f(x)dx-\int_{0}^{\alpha}\frac{f(t)}{1+g(t)}dt+\int_{0}^{\alpha}\frac{f(x)}{1+g(x)}dx=\int_{0}^{\alpha}f(x)dx$$

and the formula is proven.

Why Reflexivity cannot be deduced by Symmetry and Transitivity?

The short answer is: quantifiers matter, they’re very important.

The question was asked me by students who were starting studying equivalence relations. They wondered: why refelxivity is needed? Can’t it be deduced by Symmetry and Transitivity?

Let’s recall the definition of equivalence relation.

Given two sets $A$ e $B$, a relation is any subset of the cartesian product $A\times B$. A relation can also be defined between elements of one set $A$: in this case the relation is a subset of the cartesian product $A\times A$ ($A^{2}$).

A relation $R$ in $A\times A$ is said to be an equivalence if it is Reflexive, Symmetric e Transitive.

Reflexivity (M): $\forall x\in A, (x,x)\in R$

Symmetry (S): $(x,y)\in R \Rightarrow (y,x)\in R$

Transitivity (T): $(x,y)\in R \wedge (y,z)\in R\Rightarrow (x,z)\in R$

The reasoning made by students was like the following: S $\Rightarrow (x,y)\in R\Rightarrow (y,x)\in R$, hence, through T, $(x,x)\in R$, which looks like reflexivity M.

Looks like… The keypoint is that neither S nor T guarentee that all the elements of A are linked through R to at least one element of A: universal quantifier “for all” ($\forall$) is missed. Universal quantifier which is instead included inside reflexivity M.

In other words, reflexivity M – exactly thanks to the universal quantifier “for all” ($\forall$) – is the only property among the three which guarentees no element of A is left outside the relation R; what S and T cannot do.

It’s useful to recall that an equivalence relation on a set A naturally builds some subsets – the so called equivalence classes – which are a partition of A. So, using the definition of partition, no element of A can be excluded by the partition, that is, all elements of A must stay in one of the partition subsets.

Now, an example. The relation defined as follows:

$R:\left \{(m,n)\in \mathbb{Z}^{2} : mn>0\right \}$

is obviously symmetric and transitive; moreover almost all the elements of $\mathbb{Z}$ are linked to themselves through $R$. By the way the relation is not reflexive since $0\in\mathbb{Z}$ is not linked to itself through $R$ (indeed it’s not linked to any other element of $\mathbb{Z}$).

Should you have any comments, doubts or questions, feel free to leave them in the comments section. Thank you. See you soon.

INFINITE SERIES-PARALLEL RESISTORS CONNECTION

In this brief article, we’ll see how to find the equivalent resistance of the following net:

Let’s call REQ the equivalent resistance we’re requested to evaluate.

If we cut the net as indicated by the dotted arrow in the picture below, we can observe that the equivalent resistance of the part of the net on the right of the dotted line is again REQ

So, we can write:

$R_{EQ}=aR+bR||R_{EQ}$,

$R_{EQ}=aR+\frac{bR\cdot R_{EQ}}{bR+{R_{EQ}}}$,

$(bR+R_{EQ})R_{EQ}=aR(bR+R_{EQ})+bRR_{EQ}$ (*)

Going on with some algebra and solving the quadratic equation, we have:

$R_{EQ}=\frac{aR}{2}(1+\sqrt{1+\frac{4b}{a}})$ (1)

Let’s have now a glance to few special cases.

  1. $a=0$. In this case, all the $aR$ resistances are short circuits, that means that the overall resistance will be zero. Indeed, if we put $a=0$ in (*) we get $R_{EQ}=0$.
  2. $b=0$. In this case, all the $bR$ resistances will be 0, therefore all the resistors on the right of the first $bR$ will be shorted. Hence, the overall equivalent resistance will be only $aR$. Indeed, if we put $b=0$ in (1), we get $R_{EQ}=aR$.
  3. Finally, let’s consider the case $a=b\neq0$. If we substitute in (1), we quickly have:

$R_{EQ}=\frac{1+\sqrt{5}}{2}R \cong 1.618R$ (2)

Many of you should have noticed the “golden number” ($\frac{1+\sqrt{5}}{2}$) in (2). It seems it’s hidden everywhere…

Let’s see another way to get the same result as (2), which should provide another reason why the “golden number” is appearing in the equivalent resistance expression.

Let’s build the equivalent resistance step by step. Let’s recall we’re now considering the net made by all equale resistors ($R$)

In the first step, let’s calculate the equivalent resistance as if the net was made of the first 2 resistors only. It is:

$R_{EQ,1}=2R=\frac{2}{1}R$

In the second step, let’s add one couple of resistors (one series and one parallel). We have:

$R_{EQ,2}=R+R||2R=R+\frac{2R^{2}}{3R}=\frac{5}{3}R$

In the third step, let’s add one more couple of resistors (one series and one parallel). We have:

$R_{EQ,3}=R+R||(R+R||2R)=R+R||\frac{5}{3}R=R+\frac{(\frac{5}{3}R^{2})}{\frac{8}{3}R}=R+\frac{5}{8}R=\frac{13}{8}R$

Going on few steps, we’ll get the following sequence:

$\left \{R_{EQ,n}\right \}=\left \{ \frac{2}{1}R, \frac{5}{3}R, \frac{13}{8}R, \frac{34}{21}R, … \right \}$

This should remind us the Fibonacci’s sequence:

$f_{n}=\left \{ 1,1,2,3,5,8,13,21,34,55,… \right \}$

In fact, we have

$\left \{R_{EQ,n}\right \}=\left \{ \frac{f_{2n+1}}{f_{2n}}R \right \}$ (3)

Now, since the sequence (3) is a sub-sequence of $\left \{ \frac{f_{n+1}}{f_{n}}R \right \}$ (i.e. the sequence of ratios of 2 adjacent Fibonacci’s sequence terms) whose limit is the golden number, we have:

$R_{EQ}=\lim_{n}R_{EQ,n}=\lim_{n}\frac{f_{2n+1}}{f_{2n}}R=\lim_{n}\frac{f_{n+1}}{f_{n}}R=\frac{1+\sqrt{5}}{2}R$,

which is the same result as (2).

Kinematics and dynamics of a falling body: a traditional problem

Problem statement

A 60kg man dives in a pool from a 10m trampoline.

Assuming he starts being still and neglecting his upwards jump, find his velocity when he reaches the water.

Find the average force the water exerts on him, if he​​ stops at 5m under water.

Fig.1

In the picture, a​​ reference system​​ has been chosen and the​​ origin​​ (O) has been fixed at the water level. Since the motion happens along one direction only (vertical direction), we need to use only one vertical axis, the traditional ‘y’ axis, on which the upward arrow has been chosen as the positive orientation of the axis: this means that all vectors directed upwards will be positive while all vectors directed downwards will be negative.

Let’s assume, since there’s no mention in the problem statement, that there’s​​ no air friction. This hypothesis, used in all basic physics courses, will significantly simplify the problem solution.

Motion can be divided in 2 parts:

  • Motion in the air

  • Motion in the water

So, we’ll divide the problem solution in 2 parts accordingly.

 

PART 1: MOTION IN THE AIR

First of all, let’s try to understand​​ which forces act on the diving man. Since we assumed no friction in the air,​​ the only force acting on the man is the gravity, that is, the man’s weight (fig. 2).

Weight is approximately constant if the man is close enough to the Earth surface, so Newton’s law assures the acceleration will be constant: g

W=mg=-mgy^

Therefore, the man will experience a​​ uniformly accelerated motion, with an acceleration

g=-9.81ms2y^

Since this​​ motion is in one dimension (y) – for simplicity of notation – we’ll avoid the vector notation (y^) unless necessary.

Fig.2

The time law is:

y=y0+v0t-12gt2

Where:

y0=h=10m,v0=0,g=9.81ms2

That is:

y=h-12gt2

Setting​​ y=0​​ (water level), we can get the time at which the man will touch the water:

0=h-12gt2  

 

t= 2hg

(1)

In a constant acceleration motion, the speed-acceleration relationship is:

v=v0+at

Where​​ v0=0.​​ So, from (1):

v=at=gt= g2hg= 2hg2g=

=​​ 2gh=14ms

 

PART 2: MOTION IN THE WATER

The average force exerted by the water on the man is - by definition - a​​ constant force​​ having the same effect of the​​ real water force, that is stopping the man at 5m under the water.

So, we’ll find the constant force which stops the man at 5m under water

Fig. 3

Again, let’s try to understand​​ which forces act on the man in the water. He undergoes 2 forces (fig. 3): his​​ weight​​ W​​ and the water constant force​​ F, which can be written (in vectorial notation) as follows

W=mg=-mgy^

F=Fy^

The Newton’s dynamics law can be written as:

W+F=ma

and, since both the weight and the water force are constant, the man acceleration in the water will be constant too.

So we have a​​ constant deceleration motion, with starting velocity

v0=-14msy^

Again, motion is in one dimension (y) so, we’ll avoid the vector notation (y^) unless necessary.

So, space and velocity laws are:

s=s0+v0t+12at2v= v0+at

Where​​ s0=0,​​ v0=-14ms​​ (directed downwards), acceleration a is​​ unknown but it’s directed upwards since the man stops.

We need to solve previous equations for​​ v=0​​ (the man stops) and​​ s=p=-5m.​​ So, we need to solve

-5=-14t+12at20=-14+at

From the second equation we have​​ at=14. Substituting in the first, we get

-5=-14t+142t  

  t=0.71s

Substituting​​ t=0.71s in the second equation, we​​ get

a=19.61ms2,

directed upwards.

Going back to the Newton’s dynamics law, we have:

W+F=ma

mg+F= ma

F= ma -mg

F= ma -mg=ma -g=

=60kg19.6ms2--9.81ms2y^=

=60kg×29.41ms2y^=1765Ny^