Feuille 5 : Arithm´etique - Claude Bernard University Lyon 1

Exercice 1 Montrer que pour tout n 2 N : 1 n(n+1)(n+2)(n+3) est divisible par 24, 2 n(n+1)(n+2)(n+3)(n+4) est divisible par 120 Exercice 2 D´eterminer les couples d’entiers naturels de pgcd 35 et ppcm 210 Exercice 3 D´eterminer les couples d’entiers naturels de pgcd 18 et de somme 360 De mˆeme avec pgcd 18 et produit 6480

Soit n N n 1 2n 1

lui-m^eme Par exemple 6 est parfait : 6 =1+2+3 Montrer que si 2n+1 −1 est un nombre premier alors 2 n(2 +1 −1) est parfait Culturel : Ce r esultat est d ej a dans les el ements d’Euclide La r ecip est vraie : un nombre parfait pair est toujours de la forme pr ec edente, c’est un r esultat du^ a Euler 1

n IN ; 2

a) Le nombre 4 3 n 4n est divisible par 5 quel que soit n de IN b) Le nombre 3 2 n 2n est divisible par 7 quel que soit n de IN c) Le nombre 3 5 2 n 1 2 3 n 1 est divisible par 17 quel que soit n de IN Exercice Maths-inter ma 4 Montrer par récurrence que pour tout n de IN a) Le nombre 4 n 15 n 1 est divisible par 9 quel que soit n de IN

Exercice 1 : D ur

c) D eterminer l’ensemble des entiers n tels que (n 1)(2n + 1) divise (n + 3)(n2 + 2n 2) Exercice 2 : Les parties 1, 2 et 3 sont ind ependantes 1 a) Montrer que pour tout n 2N; (9n 1) est divisible par 8 b) En d eduire que pour tout n 2N; (32n+1 3) est divisible par 8 c) D eterminer alors le reste de la division euclidienne de 32015 et

EXERCICES - bagbouton

2) Montrer que pour tout entier non nul, 322nn est divisible par7 EXERCICE 2 : Déterminer tous les couples d’entiers naturels a et b tels que ab 1 18 2 EXERCICE 3 : Soit n un entier naturel 1) Montrer que si n est pair alors n2 est pair 2) Montrer que si est impair alors est impair 3) En déduire que est pair si et seulement si est pair et

L1 - PCP - DETERMINANTS (COURS-EXERCICES)

1n det(A1n) où A1i est la matrice 5 2 7 2 5 5 est aussi divisible par 17 En eﬀet, montrer que det(λA) =

Notion d’arithmétique et l’Ensemble des nombres entiers

Montrer que si est impair alors a2 est un nombre impair Solution : est impair alors : ak 21 avec a k k k k k2 2 2 u u 2 1 2 2 2 1 1 4 4 1 2 Donc : a k k k22 2 2 1 2 1 cc avec 2 k k k 2 cc Donc : et est un nombre impair Exercice : est un nombre impair Montrer que si est impair alors a est un nombre impair Solution : on suppose que est pair alors

Exercice 1 n N n

On veut montrer que P(n+1) est vraie Cela revient a se donner un ensemble V quelconque de n+1 vaches, et a montrer que toutes les vaches dans V ont m^eme couleur (iii) Pour montrer cela, il su t de montrer que pour tout couple (v 1;v 2) d’ el ements de V , v 1 et v 2 ont m^eme couleur Soit donc un tel couple (v 1;v 2) ∈V 2

Planche no 2 Raisonnement par récurrence : corrigé

On a montré par récurrence que : ∀n>4, n>n2 Exercice no 3 Montrons par récurrence que : ∀n>2, nest divisible par au moins un nombre premier • 2est divisible par 2qui est un nombre premier La propriété à démontrer est donc vraie quand n=2 • Soit n>2 Supposons que pour tout k∈ J2,nK, kest divisible par au moins un nombre

[PDF] Montrer que pour tout entier c : =1

[PDF] montrer que q est dénombrable

[PDF] montrer que racine de 3 est irrationnel

[PDF] montrer que racine de n est irrationnel

[PDF] montrer que se sont des rationnels

[PDF] montrer que si x appartient ? l'intervalle

[PDF] montrer que x appartient ? un intervalle

[PDF] montrer que xn 1 axn

[PDF] Montrer que y=

[PDF] MONTRER QUELQUE CHOSE SANS LE MONTRER POUR PEUT ÊTRE MONTRER TOUT AUTRE CHOSE

[PDF] Montrer registre tragique

[PDF] Montrer si le nombre A est un entier ou pas

[PDF] Montrer un défaut physique de plusieurs manières différentes comme Cyrano dans "la tirade du nez"

[PDF] montrer une inégalité avec valeurs absolues

[PDF] montrer une relation d'ordre

Universit´eClaudeBernardLyon1UEFondam entauxdesMath´em atiquesI

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisiblep ar24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Exercice2 D´eterminerlescouplesd'entiersnatu relsdepgc d35etppcm210. Exercice3D´eterminerlescouplesd'entiersnatu relsdepgcd 18etdesomme360.Demˆeme avecpgcd18 etprod uit6480.

Exercice4Calculerlepgcdde48et210,et de81et 237.Danschaque casexpr ime rl'id ent it´ede B´ezout .

Exercice5Calculerparl'algorithmed' Euclid elepgcdde18480et9828.End´eduireune ´ecriturede84 commecombinaison lin´eairede18480et9828. Exercice6Trouvertouteslessolu tionsdessyst`em essuivants dansZ 2 (a)58x+21y=1(b)14x+35y=21( c)637x+595y=29

Exercice7Notonsa=1 111111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Exercice9Combien15!admet-ilded ivi seursdansN?

Exercice10D´emontrerque,siaetbsontdesent ierspremi ersentreeux,ilenestd emˆemedesentiers a+betab. Exercice11Soienta,bdesentie rssup´erieursou´egaux`a1. Montrer: 1.(2 a 1)|(2 ab 1); 2.2 p

1pr emier)ppremier;

3.p gcd(2

a 1,2 b 1)=2 pgcd(a,b) 1. Exercice12Montrerquesinestunenti ernatur elsommededeuxcarr´e sd'entiersalorslere stedela divisioneuclidiennede npar4n' est jamais´egal`a3.

Exercice13D´emontrerquelenombre7

n +1estd ivisiblep ar8sinestimpair ;danslecasnpair,donner lerest edesadivisionpar8. Exercice14Trouverlerestedela divisi onpar13dunombre100 1000
Exercice15Trouvertouteslessolut ionsdusyst`emes uivantdansZ: n⌘13(m od19) n⌘6(m od12). 1 Exercice16SoitXl'ensembledesnombrespremiersde laforme4k+3aveck2N.

1.Mon trerqueXn'estpasvide.

2.Mon trerqueleproduitd enombresde laforme 4k+1e ste ncoredecet teforme.

3.On suppose queXestfinieton l'´ecrital orsX={p

1 ,...,p n

Soita=4p

1 p 2 ...p n

1.Mon trerparl'absurdeque aadmetundivis eurpre mierdelaforme4k+3.

4.Mon trerquececiestimpos sibleetd oncqueXestinfini.

Exercice17Soitn2N,n2.

1.Mon trerquen

2 ⌘1(m od8)sinestimpair.

2.Mon trerquen

2 ⌘0(m od8)oun 2 ⌘4(m od8)sinestpair.

3.Soi enta,b,ctroisentiersi mpairs.

i)D´ eterminerlerestemodulo8dea 2 +b 2 +c 2 etcelui de(a+b+c) 2 .End´eduirelerestemodulo

8de 2(ab+bc+ca).

ii)Existe- ilunentierm2Ntelquem 2 =ab+bc+ca?

Exercice18

Soita2Ntelquea

n +1s oit premier.M ontrerquenestdelafor men=2 k pourunent ier k2N.Qu epenserde laconjecture:2 2 n +1e stp remierpour toutentiern2N?

Exercice19

Soitpunnomb repremier.

1.Mon trerque

p i estdivisi bleparppourtouti2J1,p1K.

2.Mon trerparr´ecurencequ epourt outa2N

,l'entiera p aestdivis ibleparp.

Exercice20

1.Mon trerparr´ecurrenceq uepour toutn2Netk2N

ona: 2 2 n+k 1= 2 2 n 1 k1 Y i=0 2 2 n+i +1

2.On poseF

n =2 2 n +1.M ontr erquepourm6=n,F n etF m sontpremi ersentreeux.

3.E nd´edu irequ'ilyauneinfinit´ede nombrespremiers.

Exercice21Donnerlavaleuren basedix desnombressuivan ts:

1.(110101001)

2.(110101001)

3.(1367)

4.(1402)

Exercice22

Ecrirelesnombressui vants(donn ´esenbasedix)danslab asecibleindiqu´ee.

1.255e nbas edeux;

2.1907e nbas eseize ;

3.2016e nbas esept;

4.2000e nbas edeuxm ille.

2 Universit´eClaudeBernardLyon1UEFondam entauxdesMath´em atiquesI

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisible par24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Solution

1.24= 2·3·4.De quatre nombrescons´ecuti fs,unestdivisible par2etunautrepar4,puisqueles

r´esidusmodulo4sont0,1,2et 3.Leurproduitestdoncd ivi siblepar8. Dem ˆem e,d etroisn omb res cons´ecutifs,unestdivisiblepartrois.C omme8et 3sontpremi ersentreeux,leproduitestd ivisib le par24.

2.120 =24·5.Les r´esid usmodulo5decinqnombrescon ´scutifssont0,1,2,3et 4.Il yenadon cunequi

estdivis ibleparcinq.Comme5et24sontprem iersen treeux,leprodu itdecinqnombr esc ons´ec uti fs estdivisi blepar120. Exercice2 D´eterminerlescouplesd'entiersnatu relsdepgc d35etppcm210.

Solution

Soientaetblesdeuxn ombres.Alorsa=35a

0 etb=35b 0 ,pgc d(a 0 ,b 0 )=1eta 0 b 0 210
35
=6=2·3.Alor son acom mesolutionpour( a 0 ,b 0 ):(1,6),(2,3),(3,2)et (6,1).Cequ idonnel essolutions (35,210),(70,105), (105,70)e t(210,35). Exercice3D´eterminerlescouplesd'entiersnatu relsdepgcd 18etdesomme360.Demˆeme avecpgcd18 etpro duit6480.

Solution

1.Soi entaetblesdeuxnom bres.Alorsa=18a

0 etb=18b 0 ,pgc d(a 0 ,b 0 )=1eta 0 +b 0 360
18 =20.I lfau t donc´ecri re20comesommededeuxentie rs premierse ntreeux.Ilsn epeuv entpasˆetredi visiblespar

2ou5, ceq uid onneles solutions( 1,19),(3,17),(7,13)et (9,11)pou r(a

0 ,b 0 )ou( b 0 ,a 0 ),soit( 18,342), (54,306),(126,234)et (162,198)pou r(a,b)ou( b,a).

2.Soi entaetblesdeuxn ombres.Alorsa=18a

0 etb=18 b 0 ,pgc d(a 0 ,b 0 )=1eta 0 b 0 =6480= 18 2

·4·5.

Alorsonacomme solu tion pour(a

0 ,b 0 )ou( b 0 ,a 0 ):(1,20)et (4,5),cequ idonnel essolutions (18,360), (72,90)pou r(a,b)ou( b,a).

Exercice4Calculerlepgcdde48et210,etd e81et237. Danschaquec asexpri mer l'ide nti t´edeB ´ezout.

Solution

1.On a210=48·4+18 ;48= 18·2+12 ;18= 12+6;12= 6·2.Ain sipgcd(210,48)=6.

Onremon te:6=1812=18 (4818·2)=18 ·348=( 21048·4)·348=210 ·348·13.

2.On a237=81·2+75 ;81= 75+6;75= 6·12+3 ;6= 3·2.Ain sipgcd(237,81)=3.

Onremon te:3=756·12=75 (8175)·12= 75·1381·12=( 23781·2)·1381·12=237 ·1381·38.

Exercice5Calculerparl'algorithmed' Euclid elepgcdde18480et9828.End´eduireune ´ecriturede84 commecombinaison lin´eairede18480et9828.

Solution

Ontrav ailleavecdesr´esidusdeval eurabsoluemini male.Ona18480 =9828·21176;9828=1176·8+420;

1176=420 ·384;420=84·5.D oncpgcd(18480,9828)=84. On rem onte:

84=420 ·31176=( 98281176·8)·31176=9828 ·31176·25=9828 ·3(9828·218480)·25=

18480·259828·47.

Exercice6 Trouvertouteslessolu tionsdessyst`em essuivants dansZ 2 (a)58x+21y=1(b)14 x+35y=21( c)637x+595y=29

Solution

1.On a58=21·35;21=5·4+1. Donc pgcd (58,21)=1 eti lya unesolu tion.On re mont e:

1=21 5·4=21 (21·358)·4=58 ·421·11.Les solution ssont(x,y)2{(4+21n,1158n):n2Z}.

2.On a35=7·5et 14=7·2.Ain sipgcd(35,14)=7 ;com me7|21il yaune solu tion .Endivisan tpar

7,le syst` emeest´equivalent`a2x+5y=3.Un esol utions ´evidenteest(4,1).Less olutions sontdonc

(x,y)2{(4+5 n,12n):n2Z}.

3.On a637=595+ 42;595 =42·14+7;42=7·6.Don cpgcd(637,595)=7 ;com me7-29il n'yap as

desolut ion.

Exercice7Notonsa=1111 111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Solution

1.10bb=1111 101.Donc1111111111 =123456789·9+10.

2.p=pgc d(1111111111,123456789)=pgcd( 123456789 ,10)= 1,pu isq ue123456789estdivisibleni

par2nip ar5.

3.On a1=10·12345679123456789=(1111111111 123456789·9)·12345679123456789

=1111 111111·12345679123456789·111111112.Onadonc u=12 345679etv=

111111112.

Solution

Ondiv isepar45:Lesyst`emees t´equ ival ent `a37 x+23y=1. Ona 37=23·29;23=9·2+5;9=5·21. Doncpgcd(37 ,23)=1 eti lya unesolu tion.On re mont e:

1=5·29=( 239·2)·29=23 ·29·5=23 ·2(23·237)·5= 37·523·8.Les soluti onssont

donc(x,y)2{(5+23n,837n):n2Z}.

Exercice9Combien15!admet-ildedi vi seursdansN?

Solution

Ond´ec ompose15!enfacteurspremiers. Onc onstateai s´ementquesesfacteurs serontexactement2,3,5,7,11,13.

De1`a15, ily a7nombr esp airs.D onc2 appar aˆı taumoins7fois.Ilyaaus si3multiplesde2 2 =4.D onc

2app araˆıt3foisdeplus(aumoin s10f ois).Ilyaau ssi1mu ltiplede2

3 =8.D onc2 apparaˆıt1f oisd eplus

(aumoins 11fois).Iln'y apas demultiplesdep lusgrand espuissanc es de2.Donc 2apparaˆ ıtexactement

11foi s.Onfaitdemˆ emeave c3:ilya5m ultip lesde3,1seulmult iplede3

2 =9,e tpas depuis sancepl us

grande,donc3apparaˆı texacteme nt6 fois.Avecceraisonnement, 5apparaˆıtexactement3fois,7appar aˆı t

exactement2fois,11et13apparaˆıss ent exactement1foi sc hacun.

Donc15!=2

11 ·3 6 ·5 3 ·7 2 ·11·13.Ain si,ilya12·7·4·3·2·2pos sibilit´espourlesdiviseurspositifs.On end´ed uitque15!a4032diviseurspos itifs. Exercice10D´emontrerque,siaetbsontdesent ierspremi ersentreeux,ilenestd emˆemedesentiers a+betab.

Solution

D'abord,onremarqueque siaetbsontpremie rsentreeux,aussia 2 etb 2 lesont . Soitdundivi seurcommundeabetdea+b.Alor sddivisea(a+b)ab=a 2 .Demˆemeddiviseb 2 .D' apr`es laremar quepr´ec´edente,lese ntiersa 2 etb 2 sontpremi ersentreeux.Ainsid=±1,ce quicon clut. Exercice11Soienta,bdesentie rssup´erieursou´egaux`a 1.Montrer: 1.(2 a 1)|(2 ab 1); 2.2 p

1premier)ppremier;

3.pgc d(2

a 1,2 b 1)=2 pgcd(a,b) 1.

Solution

1.(2 ab

1)= (2

a 1)(2 aba +2 ab2a +...+2 a +1). 2

2.Si pn'estpaspremier ,alorsp=abavecaetbdeuxentiers strictementsup´erieu rs`a1.Parlepoint

1,ond ´ed uitque(2

1)n' estpaspremier.

3.D' apr`es1.,2

pgcd(a,b)

1|pgcd(2

a 1,2 b

1).D'aut repart,ilexisteu,v2N

designe sdi

´erents

telsqueau+bv=p gcd(a,b).Onsu pposesan spertedeg´en´erali t´equeu<01)|pgcd(2 au 1,2 bv

1).Orp gcd(2

au 1,2 bv

1)=p gcd( 2

au 1,2 bv 2 au pgcd(2 au 1,2 au (2 bv+au

1))=pgcd (2

au 1,2 pgcd(a,b)

1)car 2

1es timpair.D onc

pgcd(2 a 1,2 b 1)|2 pgcd(a,b)

1.D' o`uler´esultat.

Exercice12Montrerquesinestunenti ernatur elsommededeuxcarr´e sd'entiersalorslere stedela divisioneuclidiennede npar4n' est jamais´egal`a3.

Solution

Lesr´es idusmodulo4descarr´esdes nombres0,1,2,3son t0et1.

Enuti lisantlapropri´et´e

a⌘b(modn))a k ⌘b k (modn),k2N,(1) ond´ eduitquepourtoutnentiernaturel,n 2 ⌘0ou1 (mo d4) .Ceciimpliqu equele r´esidudetou tnombre naturelquiestsommed edeuxcarr´ eesd'ent iersnepeutjam aisˆet re´egale`a3.

Exercice13D´emontrerquelenombre7

n +1estd ivisiblep ar8sinestimpair; danslecasnpair,donner lerest edesadivisionpar 8.

Solution

7⌘1(m od8))7

n +1⌘(1) n +1( mod 8)⌘

0(m od8)sinestimpair;

2(m od8)sinestpair.

Exercice14Trouverlerestedelad ivisi onpar13dunombre100 1000

Solution

D'abordonnoteque100⌘9(m od13).Onend´ed uitque 100 1000
⌘9 1000
(mod13). Comme13estprem ier et9n'est pasdivisiblepar13,lepeti tth´eor eme deFermatimpliqu eque 9 12 ⌘1(m od13).

Comme1000⌘4(m od12),onobtient

9 1000
⌘9 4 ⌘(4) 4 ⌘(16) 2 ⌘3 2 ⌘9(m od13). Exercice15Trouvertouteslessolu tionsdusyst`eme suivantdans Z: n⌘13(m od19) n⌘6(m od12).

Solution

Unesolut ionparticuli`ere´ev identedusyst`emeestn=6.Com me12et19sontpre mie rsent ree ux,l'ense mble

dessoluti onsestdonn´epar{6+228 k|k2Z}. Exercice16SoitXl'ensembledesnombrespremiersde laforme4k+3aveck2N.

1.Mon trerqueXn'estpasvide.

2.Mon trerqueleproduitd enombresde laforme 4k+1e ste ncoredecet teforme.

3.On suppose queXestfinieton l'´ecrital orsX={p

1 ,...,pquotesdbs_dbs47.pdfusesText_47

[PDF] Feuille 5 : Arithm´etique - Claude Bernard University Lyon 1

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisiblep ar24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Exercice7Notonsa=1 111111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Exercice9Combien15!admet-ilded ivi seursdansN?

1pr emier)ppremier;

3.p gcd(2

Exercice13D´emontrerquelenombre7

1.Mon trerqueXn'estpasvide.

2.Mon trerqueleproduitd enombresde laforme 4k+1e ste ncoredecet teforme.

3.On suppose queXestfinieton l'´ecrital orsX={p

Soita=4p

1.Mon trerparl'absurdeque aadmetundivis eurpre mierdelaforme4k+3.

4.Mon trerquececiestimpos sibleetd oncqueXestinfini.

Exercice17Soitn2N,n2.

1.Mon trerquen

2.Mon trerquen

3.Soi enta,b,ctroisentiersi mpairs.

8de 2(ab+bc+ca).

Exercice18

Soita2Ntelquea

Exercice19

Soitpunnomb repremier.

1.Mon trerque

2.Mon trerparr´ecurencequ epourt outa2N

Exercice20

1.Mon trerparr´ecurrenceq uepour toutn2Netk2N

2.On poseF

3.E nd´edu irequ'ilyauneinfinit´ede nombrespremiers.

1.(110101001)

2.(110101001)

3.(1367)

4.(1402)

Exercice22

1.255e nbas edeux;

2.1907e nbas eseize ;

3.2016e nbas esept;

4.2000e nbas edeuxm ille.

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisible par24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Solution

1.24= 2·3·4.De quatre nombrescons´ecuti fs,unestdivisible par2etunautrepar4,puisqueles

2.120 =24·5.Les r´esid usmodulo5decinqnombrescon ´scutifssont0,1,2,3et 4.Il yenadon cunequi

Solution

Soientaetblesdeuxn ombres.Alorsa=35a

Solution

1.Soi entaetblesdeuxnom bres.Alorsa=18a

2ou5, ceq uid onneles solutions( 1,19),(3,17),(7,13)et (9,11)pou r(a

2.Soi entaetblesdeuxn ombres.Alorsa=18a

·4·5.

Alorsonacomme solu tion pour(a

Solution

1.On a210=48·4+18 ;48= 18·2+12 ;18= 12+6;12= 6·2.Ain sipgcd(210,48)=6.

2.On a237=81·2+75 ;81= 75+6;75= 6·12+3 ;6= 3·2.Ain sipgcd(237,81)=3.

Solution

1176=420 ·384;420=84·5.D oncpgcd(18480,9828)=84. On rem onte:

84=420 ·31176=( 98281176·8)·31176=9828 ·31176·25=9828 ·3(9828·218480)·25=

18480·259828·47.

Solution

1.On a58=21·35;21=5·4+1. Donc pgcd (58,21)=1 eti lya unesolu tion.On re mont e:

1=21 5·4=21 (21·358)·4=58 ·421·11.Les solution ssont(x,y)2{(4+21n,1158n):n2Z}.

2.On a35=7·5et 14=7·2.Ain sipgcd(35,14)=7 ;com me7|21il yaune solu tion .Endivisan tpar

7,le syst` emeest´equivalent`a2x+5y=3.Un esol utions ´evidenteest(4,1).Less olutions sontdonc

3.On a637=595+ 42;595 =42·14+7;42=7·6.Don cpgcd(637,595)=7 ;com me7-29il n'yap as

Exercice7Notonsa=1111 111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Solution

1.10bb=1111 101.Donc1111111111 =123456789·9+10.

2.p=pgc d(1111111111,123456789)=pgcd( 123456789 ,10)= 1,pu isq ue123456789estdivisibleni