Spécialité - Arithmétique

[upium666]

Bonjour à tous et à toutes !

J'ai sélectionné certains exercices qui circulaient sur le net et j'ai trié ceux-là parmi ceux que je ne sais pas faire, vraiment pas :

1)Pour n;)9, écrire l'algorithme d'Euclide pour prouver que PGCD(4n+3,5n+2)=PGCD(n-1,7). Quels sont les entiers n tels que PGCD(n-1,7)=7 ?
2)d=PGCD(a,b)
p,q,r,s sont des entiers vérifiant : ps-qr=1
PGCD(pa+qb,ra+sb)=?
3)Est-il possible de trouver un nombre premier p tel que p+1000 et p+2000 soient également des nombres premiers ?
4)Démontrer que n;)-12n²+16 est composé, sauf pour certaines valeurs de l'entier n que l'on déterminera

Merci de m'aider !

[Ben314]

Salut,
Pour le 1), c'est la même chose que l'algo. d'euclide qui utilise le fait que, quelque soient les entiers a,b,q on a pgcd(a,b)=pgcd(b,a-qb). Tu utilise ça pour diminuer le coeff. devant le n.
Par exemple, le début, c'est :
pgcd(5n+2,4n+3) = pgcd(4n+3,(5n+2)-(4n+3)) = pgcd(4n+3,n-1) = ...

Pour le 2), on note u=pa+qb et v=ra+sb.
Il faut évidement commencer par dire que, si d divise a et b alors il divise u et v.
Pour la réciproque, il "suffit" (???) de calculer su-qv et ru-pv.

Pour le 3), que pense tu des restes de p, p+1000, p+2000 après division par 3 ? donc...
Aide : 1003=17×59

Pour le 4), une astuce :

[upium666]

Salut,
Pour le 1), c'est la même chose que l'algo. d'euclide qui utilise le fait que, quelque soient les entiers a,b,q on a pgcd(a,b)=pgcd(b,a-qb). Tu utilise ça pour diminuer le coeff. devant le n.
Par exemple, le début, c'est :
pgcd(5n+2,4n+3) = pgcd(4n+3,(5n+2)-(4n+3)) = pgcd(4n+3,n-1) = ...

Pour le 2), on note u=pa+qb et v=ra+sb.
Il faut évidement commencer par dire que, si d divise a et b alors il divise u et v.
Pour la réciproque, il "suffit" (???) de calculer su-qv et ru-pv.

Pour le 3), que pense tu des restes de p, p+1000, p+2000 après division par 3 ? donc...
Aide : 1003=17×59

Pour le 4), une astuce :

J'ai compris, merci :lol3:

Là par contre je galère (c'était pas dans l'énoncé) :

Démontrer que pour tout n entier supérieur ou égal à 1, 30n+7 n'est jamais la somme de 2 premiers

[Lostounet]

Supposons que 30n+7 soit la somme de 2 nombres premiers.

Comme 30n + 7 est impair quel que soit n, alors c'est la somme d'un pair et d'un impair.
Le seul nombre pair premier est 2.

donc 30n + 7 = 2 + (m)

avec (m) un nombre impair premier
(m) = 30n + 7 - 2 = 30n + 5 = 5(6n + 1)

m est multiple de 5, donc m ne peut pas être premier...
A voir..

[upium666]

Supposons que 30n+7 soit la somme de 2 nombres premiers.

Comme 30n + 7 est impair quel que soit n, alors c'est la somme d'un pair et d'un impair.
Le seul nombre pair premier est 2.

donc 30n + 7 = 2 + (m)

avec (m) un nombre impair premier
(m) = 30n + 7 - 2 = 30n + 5 = 5(6n + 1)

m est multiple de 5, donc m ne peut pas être premier...
A voir..

Merci, moi j'ai proposé la démonstration suivante, pouvez-vous me dire si elle est juste ?

On suppose que pour tout n supérieur à 2, il existe p et q tels que 30n+7=p+q
30/p+q-7
p+q est congru à 7 modulo 30
p est congru à 7-q modulo 30
q=7 : premier => p non premier, absurde car p est premier
alors l'hypothèse est fausse

Mieux encore :

On suppose que pour tout n supérieur à 1, il existe p et q tels que 30n+7=p+q
n>1 => n>=2 => p+q>=67 => p>2 et q>2 or p et q sont premiers alors p et q sont impairs, alors p+q est pair :p+q=0[2]
or p+q=30n+7et 30n+7=1[2] => p+q=1[2] absurde, car p+q=0[2]
alors, l'hypothèse est fausse
Alors, pour tout n supérieur à 1, il n'existe jamais de couple (p,q) premiers tels que p+q=30n+7

[Lostounet]

Je ne comprends pas comment tu passes de p congru à 7 - q modulo 30 à q = 7?

[chan79]

Pour le 4), une astuce :

salut
je corrige juste un petit oubli d'exposant

[upium666]

salut
je corrige juste un petit oubli d'exposant

... est factorisable pour tout n alors ? or on nous demande les valeurs pour lesquelles ce n'est pas factorisable :s

[upium666]

Je ne comprends pas comment tu passes de p congru à 7 - q modulo 30 à q = 7?

J'ai pris un cas particulier
C'est faut, c'est bon :p x)

[upium666]

J'ajoute une question :
Quels sont les entiers n tels que PGCD(n-1,7)=1 ?

Merci

[Ben314]

salut
je corrige juste un petit oubli d'exposant

Oups... désolé...

... est factorisable pour tout n alors ? or on nous demande les valeurs pour lesquelles ce n'est pas factorisable :s

Oui, c'est factorisable, mais mais mais.... un nombre premier aussi "c'est factorisable" : par exemple donc... ce n'est pas complètement fini...

Quels sont les entiers n tels que PGCD(n-1,7)=1 ?

"PGCD" ça veut dire "plus grand commun diviseur".
Le PGCD(n-1,7) c'est donc en particulier un entier naturel qui divise 7. Sauf que 7 est un nombre premier.
Donc il n'y a que 2 valeurs possibles pour PGCD(n-1,7) qui sont ...
Et pour que le PGC(n-1,7)=7 ben il faut évidement que 7 divise n-1.