Counting arrays with gcd 1 I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1.
Constraints: $1 \leq A_i \leq M$ and $A_i$ should be integer.
For example:  If $N=2$ and $M=2$. We will have
1 1
1 2
2 1

3 different arrays whose gcd are 1.
 A: It is probably easiest to use inclusion/exclusion.  If $M=1$, there is only one array of size $N$ and it has gcd of $1$.  If $M=2$, there are $2^N$ arrays of size $N$, all but one of which have gcd of $1$.  The one that fails is the array with $M=1$ with every element multiplied by $2$.  Similarly, if $M=3$, there are $3^N$ arrays of size $N$, all but two of which have gcd of $1$.  As $M$ grows, you get more deductions and need to worry about double counting the deductions.  When $M=6$, for instance, there are $3^N$ arrays that have a common divisor of $2$, $2^N$ arrays that have a common divisor of $3$ and $1^N$ that have a common divisor of $5$ to avoid a gcd of $1$, but you have counted the array of all $6$'s in both the $2$ and $3$ cases, so the final value is $6^N-3^N-2^N-1^N+1^N$  Extending to large $M$, you get $$M^N-\sum_{{p \le M}_{\text{ p  prime}}}\left \lfloor \frac Mp \right \rfloor^N+\sum_{{p,q \le M}_{p\neq q\text{  prime}}}\left \lfloor \frac M{pq}\right \rfloor^N-\dots$$
A: The arrays of size $N-1$ with GCD $K$ and integer entries between $1$ $M$ are in one-to-one correspondance with arrays of size $N-1$ with GCD $1$ and integer entries between $1$ and $\lfloor M/K \rfloor$ (proof: divide by $K$).
Therefore the number $f(M,N)$ of positive integer arrays with GCD $1$ satisfies the recursion:
$$ f(M,N) = \sum_{K=1}^M \phi(K,M) f(\lfloor M/K \rfloor,N-1) $$
where $\phi(K,M)$ counts the number of integers coprime to $K$ between $1$ and $M$, i.e. the number of possibilities for the $N$th entry if the first $N-1$ have GCD $K$.
Observations about computing $\phi(K,M)$
The function $\phi(K,M)$ agrees with Euler's totient function when $K=M$:
$$ \phi(M,M) = \phi(M) $$
and of course $\phi(1,M) = M$.
For intermediate $1 \lt K \lt M$ we can offer a couple of useful observations.  If $K_1,K_2$ have the same prime divisors, then $\phi(K_1,M) = \phi(K_2,M)$.  In other words the computation of $\phi(K,M)$ depends only on the prime divisors of $K$ (and on $M$).
Second we note that $\phi(K,M)$ is (weakly) increasing as a function of $M$, with $\phi(K,0) = 0$ and $\phi(K,1)= 1$.  
Further the second argument can be reduced modulo $K$ in the following sense.  Suppose that $M = \lfloor M/K \rfloor K + R$ according to the division algorithm, $0 \le R \le K$. Then:
$$ \phi(K,M) = \lfloor M/K \rfloor \phi(K,K) + \phi(K,R) $$
In the above one can make use of the previous observation for the value $\phi(K,K)$.
Finally note that if $K$ is prime, then $\phi(K,M) = M - \lfloor M/K \rfloor$, i.e. all the values from $1$ to $M$ except the multiples of $K$.  More generally we can identify the count $\phi(K,M)$ by the inclusion/exclusion idea in Ross's approach, subtracting the count of multiples of $K$'s prime divisors individually, then adding back the count of multiples of products of prime divisors, etc.
In organizing a test computation of $f(10,10)$ I simply tabulated the values $\phi(K,M)$ for $1 \le K,M \le 10$.  It appears that only certain of the second arguments of $\phi(K,M)$ are needed in the recursion, just as only certain of the first arguments of $f(M,N)$ are needed.  In particular $M = 1,2,3,5,10$ arise from $\lfloor 10/K \rfloor$.
A: I want to calculate the number of arrays of size N, such that for each of it's element Ai,1≤Ai≤M holds, and gcd of elements of array is 1 ,with k as largest element
Constraints: 1≤Ai≤M and Ai should be integer.
For example: If N=2 and M=2 k=2
1 2
2 1 
