Lucas's theorem (original) (raw)
في نظرية الأعداد، تعبر مبرهنة لوكاس عن قسمة على عدد أولي. ظهرت مبرهنة لوكاس لأول مرة عام 1878 في مقال نشره إدوارد لوكاس.
| Property | Value |
|---|---|
| dbo:abstract | في نظرية الأعداد، تعبر مبرهنة لوكاس عن قسمة على عدد أولي. ظهرت مبرهنة لوكاس لأول مرة عام 1878 في مقال نشره إدوارد لوكاس. (ar) En teoría de números, el teorema de Lucas dice lo siguiente: (es) In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient by a prime number p in terms of the base p expansions of the integers m and n. Lucas's theorem first appeared in 1878 in papers by Édouard Lucas. (en) En théorie des nombres, le théorème de Lucas exprime le reste de la division du coefficient binomial par un nombre premier p en termes du développement en base p des entiers m et n. Le théorème de Lucas a été publié en 1878 par Édouard Lucas. (fr) 뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Lucas)의 이름이 붙어 있다. 이 정리는 어떤 조합의 수를 소수 p에 대해 법 p 상에서 구할 때 간편한 계산 방식을 제공한다. 에두아르 뤼카가 처음 이 정리를 발표한 것은 1878년 논문에서였다. (ko) In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale per un numero primo in termini dell'espansione in base dei numeri interi e . Il teorema di Lucas apparve per la prima volta nel 1878 in articoli di Édouard Lucas. (it) Em teoria dos números, o teorema de Lucas, publicado em 1878 por Édouard Lucas, afirma o seguinte: Sejam m e n números inteiros não negativos, p um número primo e sejam e os desenvolvimentos de m e n, respetivamente, na base p. Então onde denota o coeficiente binomial de m sobre n. Em particular, o coeficiente binomial é divisível por um número primo p tal como por pelo menos um dos dígitos de n na base p é maior que o dígito correspondente de m — Édouard Lucas, 1878. (pt) В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента на простое число p: где и — представления чисел m и n в p-ричной системе счисления. В частности, биномиальный коэффициент делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m. Теорема была впервые выведена французским математиком Эдуардом Люка в 1878 году. (ru) 在数论中，Lucas定理用于计算二项式系数被质数 p 除的所得的余数。 卢卡斯定理首次出现在1878年爱德华·卢卡斯的论文中。 (zh) У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта на просте число p: де і — подання чисел m і n у p-ковій системі числення. Зокрема, біноміальний коефіцієнт ділиться на просте число p націло тоді й лише тоді, коли хоча б одна p-кова цифра числа n перевищує відповідну цифру числа m. Теорему вперше вивів 1878 року французький математик Едуард Люка. (uk) |
| dbo:wikiPageExternalLink | http://nntdm.net/papers/nntdm-18/NNTDM-18-4-01-06.pdf |
| dbo:wikiPageID | 7879246 (xsd:integer) |
| dbo:wikiPageLength | 7101 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094274419 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binomial_coefficient dbc:Theorems_about_prime_numbers dbr:Remainder dbr:P-adic_valuation dbc:Articles_containing_proofs dbr:Modular_arithmetic dbr:Édouard_Lucas dbr:Parity_(mathematics) dbr:Number_theory dbr:Radix dbr:Prime_number dbr:Bit dbr:Positional_notation dbr:Kummer's_theorem dbr:Carry_(arithmetic) dbr:Binary_expansion |
| dbp:drop | hidden (en) |
| dbp:proof | Let M be a set with m elements, and divide it into mi cycles of length pi for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups Cpi acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Thus in order to compute modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly ni cycles of size pi. Thus the number of choices for N is exactly . (en) This proof is due to Nathan Fine. If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient : is divisible by p but the denominator is not. Hence p divides . In terms of ordinary generating functions, this means that : Continuing by induction, we have for every nonnegative integer i that : Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that for some nonnegative integer k and integers m'i with 0 ≤ m'i ≤ p-1. Then : where in the final product, ni is the ith digit in the base p representation of n. This proves Lucas's theorem. (en) |
| dbp:title | Combinatorial proof (en) Lucas's Theorem (en) Proof based on generating functions (en) |
| dbp:urlname | LucassTheorem (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_arXiv dbt:Cite_journal dbt:For dbt:Reflist dbt:Math_proof dbt:PlanetMath |
| dct:subject | dbc:Theorems_about_prime_numbers dbc:Articles_containing_proofs |
| rdfs:comment | في نظرية الأعداد، تعبر مبرهنة لوكاس عن قسمة على عدد أولي. ظهرت مبرهنة لوكاس لأول مرة عام 1878 في مقال نشره إدوارد لوكاس. (ar) En teoría de números, el teorema de Lucas dice lo siguiente: (es) In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient by a prime number p in terms of the base p expansions of the integers m and n. Lucas's theorem first appeared in 1878 in papers by Édouard Lucas. (en) En théorie des nombres, le théorème de Lucas exprime le reste de la division du coefficient binomial par un nombre premier p en termes du développement en base p des entiers m et n. Le théorème de Lucas a été publié en 1878 par Édouard Lucas. (fr) 뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Lucas)의 이름이 붙어 있다. 이 정리는 어떤 조합의 수를 소수 p에 대해 법 p 상에서 구할 때 간편한 계산 방식을 제공한다. 에두아르 뤼카가 처음 이 정리를 발표한 것은 1878년 논문에서였다. (ko) In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale per un numero primo in termini dell'espansione in base dei numeri interi e . Il teorema di Lucas apparve per la prima volta nel 1878 in articoli di Édouard Lucas. (it) Em teoria dos números, o teorema de Lucas, publicado em 1878 por Édouard Lucas, afirma o seguinte: Sejam m e n números inteiros não negativos, p um número primo e sejam e os desenvolvimentos de m e n, respetivamente, na base p. Então onde denota o coeficiente binomial de m sobre n. Em particular, o coeficiente binomial é divisível por um número primo p tal como por pelo menos um dos dígitos de n na base p é maior que o dígito correspondente de m — Édouard Lucas, 1878. (pt) В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента на простое число p: где и — представления чисел m и n в p-ричной системе счисления. В частности, биномиальный коэффициент делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m. Теорема была впервые выведена французским математиком Эдуардом Люка в 1878 году. (ru) 在数论中，Lucas定理用于计算二项式系数被质数 p 除的所得的余数。 卢卡斯定理首次出现在1878年爱德华·卢卡斯的论文中。 (zh) У математиці теоремою Люка́ називають таке твердження про остачу від ділення біноміального коефіцієнта на просте число p: де і — подання чисел m і n у p-ковій системі числення. Зокрема, біноміальний коефіцієнт ділиться на просте число p націло тоді й лише тоді, коли хоча б одна p-кова цифра числа n перевищує відповідну цифру числа m. Теорему вперше вивів 1878 року французький математик Едуард Люка. (uk) |
| rdfs:label | مبرهنة لوكاس (ar) Teorema de Lucas (es) Théorème de Lucas (fr) Teorema di Lucas (it) Lucas's theorem (en) 뤼카의 정리 (ko) Teorema de Lucas (pt) Теорема Люка (ru) Теорема Люка (uk) 卢卡斯定理 (zh) |
| owl:sameAs | yago-res:Lucas's theorem wikidata:Lucas's theorem dbpedia-ar:Lucas's theorem dbpedia-es:Lucas's theorem dbpedia-fr:Lucas's theorem dbpedia-it:Lucas's theorem dbpedia-kk:Lucas's theorem dbpedia-ko:Lucas's theorem dbpedia-pt:Lucas's theorem dbpedia-ru:Lucas's theorem dbpedia-uk:Lucas's theorem dbpedia-zh:Lucas's theorem https://global.dbpedia.org/id/EnM9 |
| prov:wasDerivedFrom | wikipedia-en:Lucas's_theorem?oldid=1094274419&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Lucas's_theorem |
| is dbo:knownFor of | dbr:Édouard_Lucas |
| is dbo:wikiPageRedirects of | dbr:Lucas'_theorem dbr:Lucas_theorem |
| is dbo:wikiPageWikiLink of | dbr:Symmetric_Boolean_function dbr:Édouard_Lucas dbr:Fracton_(subdimensional_particle) dbr:Kummer's_theorem dbr:List_of_theorems dbr:Lucas'_theorem dbr:Lucas_theorem |
| is dbp:knownFor of | dbr:Édouard_Lucas |
| is foaf:primaryTopic of | wikipedia-en:Lucas's_theorem |