A Rigorous Proof For Solving The Problem: Why The Solution Works, From Proof to Pseudocode
Note: In this proof, a notable amount of subscript is used. However since it is not exactly feasible to properly format the subscript, instead array index is us
Note: In this proof, a notable amount of subscript is used. However since it is not exactly feasible to properly format the subscript, instead array index is used in place of subscript. For example, `t[i]` will be used instead of t<sub>i</sub>.

The explanation in this proof will be divided into the following parts:

**Section 1: Foundation**
**Section 2: Proof for Solution to The Problem**
**Section 3: Pseudocode to Solution**

> Note:
> - If you got the solution but wondering why it works like that, Section 2(b) explains why the solution works
> - If you solved the problem with some intuition and you found it worked but can't put a finger why, Section(c) explains the more "feel"-y approach.

_Jump to the end of the post to see the TLDR version._
 
# **Section 1: Foundation**
 ___

To begin, the foundation for the proof is to be laid out. First, the congruence relation (`≡`) and some of its properties are presented

**Definition:** `a ≡ r (mod d)` is an expression equivalent to the equation `a = qd + r` where:
- `q` (quotient) is an integer that follows `q = floor(a / d)`,
- `d` (divisor) is a variable integer
- `r` (remainder) is an integer that follows `r = a modulo d`, `0 ≤ r, < d`
- `a` is variable integer, particularly serves as dividend.

This expression and equation stems from a division operation: `a / d`.

**Example:** Suppose a division operation is given as follows:
```c
29 / 8
```
By definition, the quotient and remainder can be found:
```c
q = floor(29 / 8)
q = 3

r = 29 modulo 8
r = 5
```
Equivalently, this can be represented as:
```c
29 = 3(q) * 8(d) + 5(r)
```
or
```
29 ≡ 5 (mod 8)
```

**Definition:** Addition, subtraction, and multiplication operation on integers preserves their congruence relation.

**Example:** Addition. Suppose the following equation in a congruence system of 4 (i.e. `... ≡ ... (mod 4)`:
```c
5 + 10
```
The congruence relation of the equation's outcome is equal to adding each of the element's congruence in the equation.
```
The congruence relation of the equation's outcome
5 + 10 = 15
15 ≡ 3 (mod 4)

Adding each of the element's congruence
5 ≡ 1 (mod 4)
10 ≡ 2 (mod 4)
1 (mod 4) + 2 (mod 4) = 3 (mod 4)
```

**Example:** Subtraction. Suppose the following equation in a congruence system of 7 i.e. (`... ≡ ... (mod 7)`:
```c
16 - 3
```
The congruence relation of the equation's outcome is equal to subtracting the element's congruence in the equation.
```
The congruence relation of the equation's outcome
16 - 3 = 13
13 ≡ 6 (mod 7)

Subtracting each of the element's congruence
16 ≡ 2 (mod 7)
3 ≡ 3 (mod 7)
2 (mod 7) - 3 (mod 7) = -1 (mod 7)
2 (mod 7) - 3 (mod 7) = 6 (mod 7)
```
In the last line, the equation underflows back to positive because `r` is limited to be `0 ≤ r < d`.

**Example:** Multiplication. Suppose the following equation in a congruence system of 9 i.e. (... ≡ ... (mod 9)`):
```c
20 * 16
```
The congruence relation of the equation's outcome is equal to multiplying each of the element's congruence in the equation.
```c
The congruence relation of the equation's outcome
20 * 16 = 320
320 ≡ 5 (mod 9)

Multiplying each of the element's congruence in the equation.
20 ≡ 2 (mod 9)
16 ≡ 7 (mod 9)
2 (mod 9) * 7 (mod 9) = 14 (mod 9)
2 (mod 9) * 7 (mod 9) = 5 (mod 9)
```
In the last line, the answer is reduced down so that 14 is under 9, because `r` is limited to be `0 ≤ r < d)`.

**Theorem I: Bezout Identity (special case, reworded).** There exists some pair of integer `(p, q)` such that given two integer `a` and `b` where both are coprime (i.e. `gcd(a, b) = 1`), the equation `1 = ab + pq` can be made. [1, with modification]

*Proof*
First, the following equation is formally presented, By definition,
```
gcd(a, b) = 1
1 = ab + pq, for some integer pair (p, q)
```
Therefore,
```
gcd(a, b) = ab + pq, for some integer pair (p, q)    -- (1)
```
The only time two positive integers namely `a` and `b`, and for the sake of proof, `a > b`, can result in 1 by following the equation `ap + bq` for some variable `p` and `q`, is when `a` and `b` are coprime i.e. `gcd(a, b) = 1`. It is impossible to create 1 if this condition is not met, because when `g = gcd(a, b)` and `g != 1` that means `a ≡ 0 (mod g)` and `b ≡ 0 (mod g)`. It follows that when a number `n ≡ 0 (mod g)`, its multiple will also be `0 (mod g)` i.e.

```
n ≡ 0 (mod g)
n * x ≡ 0 * x (mod g), for some integer x
nx ≡ 0 (mod g), for some integer x
```
Therefore both `a` and `b` will not have any multiple that when divided by `g` will result in some remainder.

Adding (and subtracting) `a` and `b` will also result in `0 (mod g)` i.e.

```
a + b ≡ (0 + 0) (mod g)
a + b ≡ 0 (mod g)
```
```
a - b ≡ (0 - 0) (mod g)
a - b ≡ 0 (mod g)
```
All of this lead to the conclusion that all arithmetical operation except division using `a` and `b` all will result in a number multiple of `g`. This implies that it is impossible to generate a number other than `g` and its multiple. And since `g != 1` it is impossible to generate an integer 1 altogether. Therefore, it is necessary for `g = 1`, where `g = gcd(a, b)`, holds true to generate 1. ■

# Section 2: Proof for Solution to The Problem
___

We will split this section into the following parts:

Part (a) - Establishing Problem Function Statement
Part (b) - Proving Hypothesis I: Finding the relation between solving `gcd` functions to the original problem statement
Part (c) - Proving Hypothesis II: Figuring out if nesting `gcd` function will result in a highest common factor between all parameters used.

## Part A - Problem Function Statement
To start, the following statement in the problem will be formulated into mathematical expression:
> ...multiply each element by an integer and add all these numbers...

The above statement is equal to:

![image.png](https://assets.leetcode.com/users/images/db7a9dd0-ab71-400f-bc46-b6d1a478acd9_1734889046.9345746.png)

where `c` are free variables and `i` are some selected number from `nums`.

## Part B - Hypothesis I:
> Solving for nested `gcd` function(s) is equivalent to solving the problem.

### *Proof*
To prove the hypothesis, this section attempts to figure out whether solving for `gcd` function will end up with the problem function statement (equation (2)).

The following parts will explain the cases needed to prove the hypothesis.

*Case 1: Supplying one `gcd` function as a `gcd` argument.*

![image.png](https://assets.leetcode.com/users/images/3634278c-9572-4d36-b380-a6138c7d46b3_1734889037.7069895.png)


where `c` are free variable.

Equation (3) can be expanded into the following.

![image.png](https://assets.leetcode.com/users/images/a82bff8d-1a91-40a0-a45c-6fde22c550e8_1734888180.040043.png)

where `c`, `p`, `q` are some free variables. It can be seen easily that **equation (4) follows the form of problem function statement (equation (2)).**


**Corollary I:** The variation where the `gcd`-as-argument is supplied into the first position of the outer `gcd` follows the same reasoning, and will end up with the same conclusion stated above.

*Case 2: Supplying two `gcd` function as a `gcd` argument.*
(Note: I kinda forgot why I explain this in the first place, but I'll leave this as is because why not lol.)

Consider the following equation.

![image.png](https://assets.leetcode.com/users/images/0b5c0e6b-c00b-4165-bb28-6be4e0f68f3a_1734887962.4888144.png)


where `c` is a free variable. Once again, **equation (5) follows the form of problem function statement (equation (2)).** This shows that solving `gcd(gcd(m, n), gcd(o, p))` for some `m`, `n`, `o`, and `p` is equivalent to solving the problem function statement (equation (2)).

Therefore, solving a nested `gcd` function will result in the problem function statement. The hypothesis is proven true. ■


**Corollary II:** `gcd` of two number can be used as an intermediary value for some next iteration of `gcd` function when solving the problem.

___

It has been established that the solution to the problem can be reduced to whether it is possible to find any set of number in `nums` such that their `gcd` is 1.

It should be relatively easy to intuitively deduce that the value `v` from equation (5) is in fact the `gcd` to all input in question. Nevertheless, the next part will discuss the correctness of the following hypothesis. This is for the sake of completeness of the proof along with providing the correctness of the algorithm to solve the problem.

___

## Part C - Hypothesis II
> `gcd` function with more than two parameters can be built on `gcd` function with two parameters:
$$
\begin{align}
\gcd(a, b, c) = \gcd(\gcd(a, b), c)
\end{align}
$$

### *Proof*
The hypothesis will be proved using two lemmata:

#### *Lemma I - Common divisibility*
> Given $w = \gcd(\gcd(a,\ b),\ c)$, `w` divides `a`, `b`, and `c`.

Corollary II states that the `gcd` of two input can be used as the input of another `gcd` function. This corollary can be utilized to find the `gcd` of a set of number (instead of only two).

Consider the following equation.
$$
\begin{align}
\gcd(a, b) = v
\end{align}
$$

By definition, this means that:
(1) `v` divides `a`
(2) `v ≤ a` as direct consequence of (1)
(3) `v` divides `b`
(4) `v ≤ b` as direct consequence of (2)
(5) There is no arbitrary `n` where `n > v` such that `n` divides both `a` and `b`

Next, consider the following equation.
$$
\begin{align}
\gcd(v, c) = w
\end{align}
$$
By definition, this means that:
(6) `w` divides `v`
(7) `w ≤ v` as direct consequence of (6)
(8) `w` divides `c`
(9) `w ≤ c` as direct conseuquence of (9)
(10) There is no arbitrary `n` where `n > w` such that `n` divides both `v` and `c`

Divisibility is transitive. Meaning, if `x` divides `y` and `y` divides `z`, then `x` divides `z` (for additional reading material, see [2]). Returning to the previous findings,

(6) `w` divides `v` + (1) `v` divides `a` → (11) `w` divides `a`
(6) `w` divides `v` + (3) `v` divides `b` → (12) `w` divides `b`

Therefore, given
$$
\begin{align}
\gcd(a, b) &= v \\
\gcd(v, c) &= w
\end{align}
$$
We have the following properties:
(8) `w` divides `c`
(11) `w` divides `a`
(12) `w` divides `b`

This proves that `w` is a common divisor of `a`, `b`, and `c`.

#### *Lemma II - No higher solution possible*
> Given $w = \gcd(\gcd(a,\ b),\ c)$, there can be no arbitrary `x` where `x > w` such that `x` divides `a`, `b`, and `c`.

What is left to do now is to show that `w` is in fact the greatest value possible for `a`, `b`, and `c`. This easily follows using the definition of `gcd` (meaning, the below statements hold true by definition)

(5) There is no arbitrary `n` where `n > v` such that `n` divides both `a` and `b`
(7) `w ≤ v` as direct consequence of (6)
(10) There is no arbitrary `n` where `n > w` such that `n` divides both `v` and `c`

Using these statements, the following premises can be derived:

##### First Derived Premise
Since (7) `w ≤ v` and (5) there is no arbitrary `n` where `n > v` such that `n` divides both `a` and `b`, that means:

(13) There is no arbitrary `n` where `n > w` such that `n` divides both `a` and `b`.

##### Second Derived Premise

We have these two premises:
(10) There is no arbitrary `n` where `n > w` such that `n` divides both `v` and `c`
(13) There is no arbitrary `n` where `n > w` such that `n` divides both `a` and `b`.

Combining the two, we can obtain:
(14) **There is no arbitrary `n` where `n > w` such that `n|v`, `n|a`, `n|b`, and `n|c`**

Therefore, `w` is in fact the biggest value possible that can factor `a`, `b`, and `c`. ■

#### Wrap-up
By combining the two lemma:
Lemma I: Given $w = \gcd(\gcd(a,\ b),\ c)$, `w` divides `a`, `b`, and `c`.
Lemma II: Given $w = \gcd(\gcd(a,\ b),\ c)$, there can be no arbitrary `x` where `x > w` such that `x` divides `a`, `b`, and `c`.
it can be concluded that chaining 2-ary `gcd` function will output the greatest common divisor for all the input in question. That is,

$$
\begin{align}
\gcd(a, b, \cdots, z) = \gcd(a, \gcd(b, \gcd(\cdots, z)))
\end{align}
$$

# Section 3: Pseudocode to Solution

Using Hypothesis II, the core algorithm to solve the problem can be constructed by means of the following pseudocode,

```c++
Input: nums - an array of integers

let hcf ← gcd(nums[1], nums[2])
for i from 3 to nums.length:
	hcf ← gcd(hcf, nums[i])
if hcf equal to 1:
	return true
else:
	return false
```
Variation can be made, for example, to quit early when at one point it has been established that `hcf` is 1. The `gcd` function implementation can use the Euclidean Algorithm [4].

___

# TLDR version:
1. The problem boils down to finding out if the GCD of any combination of elements in `nums` is equal to 1
    - Why:
        - The Euclidean Algorithm gives GCD of two numbers
        - In doing so, if we have `a` and `b`, Euclidean Algorithm guarantees the existence `p` and `q` that gives `gcd(a, b)` like so: $ap + bq = \gcd(a,\ b)$
        - Put the other way: if we know the value of $\gcd(a,\ b)$, it is guaranteed that there exists value pair `p` and `q` that gives $ap + bq = \gcd(a,\ b)$
        - If we can find certain `a` and `b` that yields $\gcd(a,\ b) = 1$, we automatically solve the problem.
            - Isn't it great? We don't have to find the `p` and `q` themselves to solve the problem! Just need to find the right `a` and `b`.
    - Key takeaway: forget the problem statement and just solve for GCD. Solving one will solve the other.
2. GCD function classically accepts only two parameters. Will it work if the function accepts many parameters?
    - Yes.
    - Do it like so: `gcd(a, b, c) = gcd(gcd(a, b), c)`.
        - We can do it like this too if we want: `gcd(a, b, c) = gcd(a, gcd(b, c))`
    - Why:
        - GCD function returns a value `v` that has this properties:
            1. `v` divides all of the parameter.
            2. There is no integer bigger than `v` that can do point (a).
        - Division is transitive: if `a` divides `b`, and `b` divides `c`, then `a` divides `c`.
            - Example: 10 divides 200, and 200 divides 2400. Therefore 10 divides 2400.
        - Given `v = gcd(a, b)`, what happen if we set `a = gcd(x, y)`?
            - First, we have `v` divides `a` and `b`.
            - Then we have `a` divides `x` and `y`.
            - Division is transitive, meaning: `v` divides `x` and `y`.
        - Therefore:
            1. `v` divides `x`, `y`, and `b`
            2. There is no integer bigger than `v` that can do point (a)
        - This is the very same properties of GCD isn't it? See the first point of "Why?".
            - Therefore: chaining GCD function inside it gives the highest common factor for all inputs used.
3. In conclusion the following step will yield the correct answer:
    1. Put all value in `nums` into GCD function (point 2)
    2. Check if the result is 1 (point 1)

Reference:
[1] Bezout's Identity, https://en.wikipedia.org/wiki/Bézout%27s_identity (accessed at 24th May 2022)
[2] Properties of Divisibility, https://ccssmathanswers.com/properties-of-divisibility/ (accessed at 24th May 2022)
[3] Greatest Common Divisor, https://en.wikipedia.org/wiki/Greatest_common_divisor (accessed at 25th May 2022)
[4] Euclidean Algorithm, https://en.wikipedia.org/wiki/Euclidean_algorithm#Procedure (accessed at 25th May 2022)

<small>Here's hoping for LaTeX typesetting support</small>
['Math', 'Number Theory']