Python sol by G.C.D. & Bézout Lemma 90%+ [w/ Hint]
Python sol by Greatest Common Divisor & B\xE9zout Lemma\n\n---\n\nHint:\n\nRecall that for integer a, b\naX + bY = k has integer solution (X, Y) if k is multipl
Python sol by Greatest Common Divisor & B\xE9zout Lemma\n\n---\n\n**Hint**:\n\nRecall that for integer a, b\naX + bY = k has integer solution (X, Y) if k is multiple of gcd(a, b) from **[B\xE9zout lemma](https://proofwiki.org/wiki/B\xE9zout\'s_Lemma)**\n\nIn addition, [description](https://leetcode.com/problems/check-if-it-is-a-good-array/) sets k = 1, which means gcd(a,b) | 1.\ngcd(a,b) | 1\n=> gcd(a,b) = 1\n=> **a, b** is **co-prime**.\n\nNow, back to question itself.\n\nIf **gcd( all integers in given array) = 1**, then there exist at least one subset (a, b) satisfies aX + bY = 1. \nTherefore, input is a **good array**.\n\nOtherwise, there is no solution.\nAnd input is Not a good Array.\n\n---\n\n**Bezout Lemma**:\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1583116964.png)\n\n---\n\n**Implementation**:\n\n```\nfrom math import gcd\n\nclass Solution:\n    def isGoodArray(self, nums: List[int]) -> bool:\n        \n        \n        # ax + by = 1 has integer solution only when gcd(a, b) == 1\n        \n        x = nums[0]\n        \n\t\t# compute the greatest common divisor for all input integers\n        for number in nums:\n            \n            x = gcd(x, number)\n            \n        \n        return x == 1\n```\n\n---\n\nReference:\n\n[1] [Wiki Proof: B\xE9zout\'s Lemma](https://proofwiki.org/wiki/B\xE9zout\'s_Lemma)\n\n[2] [Python official docs about math.gcd()](https://docs.python.org/3/library/math.html?highlight=gcd#math.gcd)
['Math', 'Python']