Grade 12 - Exp. / Pgcd, prime numbers, Bezout and Gauss theorems 80 exercises (100% corrected)

a
1. Properties of prime numbers E.3363 Specify whether the following inte-gers are prime or not : a 37 b 127 c 541 d 2 × 3 × 5 × 7 + 1 E.4279 Establish that for any natural number k ( 2 k n ) , the integer n !+ k is not a prime number. E.6771 For any non-zero natural number n , we call S ( n ) the number equal to the sum of the positive divisors of n . 1 Check that : S (6)=12 and calculate S (7) . 2 a Show that, for any natural number n greater than or equal to 2 : S ( n ) 1+ n b What are the natural numbers n such that S ( n )= 1+ n ? E.6924 Below is given a function of a following algorithm où MOD(N,k) represents the remainder of the Euclidean division of N by k . Function f(a) k ← 2 As long as MOD(a;k) = 0 and k √ a k ← k+1 End As long as If k> √ a Then Return 0 Otherwise Then Return 1 End If 1 What is the value of k when this function is called with the parameter a=127 ? And if we enter a=119 ? 2 What can be said about the integer a passed as a pa-rameter when the value returned by the function f is 0 ? Justify your answer. 2. Factoring and prime numbers E.3620 Let a ∈ N , consider the expression : ( E ): a 4 − 3 a 2 +1 1 Establish the following equality: a 4 − 3 a 2 + 1 = a 2 − a − 1 · a 2 + a − 1 2 a Solve the following equations : a 2 − a − 1 = 1 ; a 2 + a − 1 = 1 b Determine for quelle (s) valeur (s) of a , the expression ( E ) defined a prime integer. E.3621 For a a natural number, consider the expression : ( F ) : a 3 − 5 a Justify that the integer ( F ) cannot be a prime number. E.8614 For a a natural number, consider the expression : ( E ) : a 3 − 5 · a 2 + 7 a 1 Express ( E ) as a product of a polynomial of degree one and a polynomial of degree two. 2 Determine the values of a for which the expression ( E ) defines a prime number. E.3633 1 Let x be a real number. a Show that : x 4 +4= x 2 +2 2 − 4 · x 2 b Deduce that x 4 +4 can be written as the product of two trinomials with integer coefficients. 2 Let n be a natural number greater than or equal to 2. Consider the following two integers : A = n 2 − 2 n + 2 ; B = n 2 + 2 n + 2 a Show that n 4 +4 is not prime. b Show that, any divisor of A that also divides n is a divisor of the number 2 . c Show that, any common divisor of A and B , divides 4 n . E.3668 1 Let x and p be two natural numbers, calculate the sum : 1 − x + x 2 + ··· +( − 1) p · x p 2 a Demonstrate that, whatever the natural numbers x and n , the integer x 2 n +1 +1 is a multiple of x +1 . b Note that if k is odd then (2 q ) k +1 is divisible by 2 q +1 . 3 Let m be a natural number. Proving the hypothesis ˇ m is a power of 2 ı is a necessary condition for 2 m +1 to be a prime integer. 3. Prime numbers and congruence E.3619 Let p be a prime integer greater than or equal to 5 . 1 Justify that the integer p verifies one of the following two conditions : p ≡ 1 ( mod. 6) ; p ≡ 5 ( mod. 6) 2 Justify that the integer p 2 − 1 is divisible by 24 . https://chingmath.fr chapExoCorrec/3363 sacados/3363 chapExoCorrec/4279 sacados/4279 Extrait de Liban Juin 2010 chapExoCorrec/6771 sacados/6771 chapExoCorrec/6924 sacados/6924 chapExoCorrec/3620 sacados/3620 chapExoCorrec/3621 sacados/3621 chapExoCorrec/8614 sacados/8614 chapExoCorrec/3633 sacados/3633 chapExoCorrec/3668 sacados/3668 chapExoCorrec/3619 sacados/3619
E.3624 In this exercise, we propose to study the following problem : ˇ Can integers whose decimal writing uses only the single digit 1 be prime? ı For any natural number p 2 , we pose N p =1 ::: 1 où 1 appears p times. We therefore recall that : N p = 10 p − 1 + 10 p − 2 + · · · + 10 0 . 1 Are the integers N 2 =11 , N 3 =111 , N 4 =1111 prime? 2 Prove that N p = 10 p − 1 9 . Can we be sure that 10 p − 1 is divisible by 9 ? 3 We propose to show that if p is not prime, then N p is not prime. Recall that for any real number x and any non-zero nat-ural number n , x n − 1 = x − 1 x n − 1 + x n − 2 + · · · + x + 1 a Assume p is even and pose p =2 q , où q is a natural number greater than 1 . Show that N p is divisible by N 2 =11 . b Assume p is a multiple of 3 and pose p =3 q , où q is a natural number greater than 1 . Show that N p is divisible by N 3 =111 . c Assume p not prime and pose p = k · q où k and q are natural numbers greater than 1 . Deduce that N p is divisible by N k . 4 State a necessary condition for N p to be prime. Is this condition sufficient? 4. PGCD and decomposition into products of prime factors E.8610 1 Determine the prime factor product decomposition of the numbers 1764 and 198 . 2 Deduce the PGCD of the numbers 1764 and 198 . E.282 Definition: two integers are said to be prime of each other , if the integer 1 is the only divisor common to these two numbers. Proposition: two integers are prime to each other if, and only if, their PGCD has value 1 . 1 Determine the PGCD of the different pairs of integers : a (15 ; 21) b (18 ; 28) c (15 ; 22) 2 Determine whether the two integers 56 and 45 are prime to each other E.3721 In each case, using the decomposi- tion into products of prime factors, determine the PGCD of the pair ( a ; b ) of integers : 1 a = 35 × 21 ; b = 36 × 25 2 a = 6 2 × 12 ; b = 21 4 × 15 2 3 a = 35 280 201 ; b = 6 804 131 E.256 1 Give the product of prime factors decomposition of the following two integers : A 36 × 26 b 12 × 21 2 Deduce the PGCD of 936 and 252. 3 Reduce the fraction : 936 4 252 5 E.3723 Let n be a natural number less than 120 . Determine the set of values of n such that : pgcd ( n ; 120) = 6 5. Characteristic property of PGCD E.3724 Determine the set of pairs ( m ; n ) of natural numbers such that : pgcd ( m ; n ) =6 ; m + n =72 E.6022 Determine the set of pairs ( m ; n ) of natural integers verifying the system : S : m 2 − n 2 = 5440 pgcd ( m ; n ) = 8 E.5344 In the equation system below, the integers x and y below represent natural numbers où x<y : x · y = 135 pgcd ( x ; y ) = 3 Solve this system of equations. 6. PGCD and divisors https://chingmath.fr chapExoCorrec/3624 sacados/3624 chapExoCorrec/8610 sacados/8610 chapExoCorrec/282 sacados/282 chapExoCorrec/3721 sacados/3721 chapExoCorrec/256 sacados/256 chapExoCorrec/3723 sacados/3723 chapExoCorrec/3724 sacados/3724 chapExoCorrec/6022 sacados/6022 Lyon Juin 1977 3 points chapExoCorrec/5344 sacados/5344
E.3715 We denote by p a natural inte-ger. Consider for any non-zero natural number n the integer: A n =2 n + p . Note d n the PGCD of A n and A n +1 1 Show that d n divides 2 n . 2 Determine the parity of A n as a function of that of p . Justify. E.6021 Let n be a relative integer. 1 Note d the pgcd of the integers 9 n +4 and 2 n − 1 . Justify that d divides 17 . 2 Establish the following equivalence : n ≡ 9 ( mod. 17) ⇐⇒ pgcd (9 n +4 ; 2 n − 1)=17 E.6076 For any natural number n , consider the two integers ¸ and ˛ defined by: ¸ =2 n +1 ; ˛ = n +3 Let d be the pgcd of the integers ¸ and ˛ : d = pgcd ( ¸ ; ˛ ) 1 a Justify that the integer d is a divisor of 5 b What are the possible values of d ? 2 Establish the following equivalence : ¸ and ˛ are multiples of 5 ⇐⇒ n − 2 is multiple of 5 . E.4272 For any natural number n greater than or equal to 2 , we pose : A ( n ) = n 4 + 1 1 Study the parity of the integer A ( n ) . 2 Show that, whatever the integer n , A ( n ) is not a multiple of 3 . 3 Show that any integer d divisor of A ( n ) is prime with n . 4 Show that, for any integer d divisor of A ( n ) : n 8 ≡ 1 ( mod. d ) 7. PGCD reduction E.3722 Proposition: (lemma for Euclid’s algorithm) be a and b two non-zero relative integers and for any relative integer k such that a + k · b is non-zero, we have : pgcd ( a ; b ) = pgcd ( a + k · b ; b ) 1 Determine the PGCD of two consecutive even natural numbers. 2 Determine the PGCD of two consecutive odd natural numbers. E.3720 For any natural number n not equal to zero, we consider the integers : a n = 4 × 10 n − 1 ; b n = 2 × 10 n − 1 ; c n = 2 × 10 n +1 1 Calculate a 1 , b 1 , c 1 , a 2 , b 2 , c 2 , a 3 , b 3 and c 3 . 2 How many digits do the decimal representations of the integers a n and c n have? Show that a n and c n are divisible by 3 . 3 Show, using the list of prime numbers less than 100 given below, that b 3 is prime. 4 Monstrate that, for any non-zero natural number n : b n × c n = a 2 n . Deduce a prime factor product decomposition of a 6 . 5 Show that : pgcd ( b n ; c n )= pgcd ( c n ; 2) . Deduce that b n et c n sont prime to each other. List of prime integers less than 100 : 2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 29 ; 31 ; 37 ; 41 ; 43 ; 47 ; 53 ; 59 61 ; 67 ; 71 ; 73 ; 79 ; 83 ; 89 ; 97 E.5300 Consider two natural numbers x and y . Show that if x and y are prime to each other then so are the integers 2 x + y and 5 x +2 y . E.5729 Consider the two integers A =10 n +7 and B =2 n +1 . 1 Determine the real integers a and b verifying the equal-ity: 10 n + 7 2 n + 1 = a + b 2 n + 1 2 Justify that the integers A and B are prime to each other. E.6025 1 a Assuming that a =9 p +4 q and b =2 p + q , show that the integers a and b on the one hand ; p and q on the other have the same PGCD. b Demonstrate that the integers 9 p +4 and 2 p +1 are prime to each other. 2 Determine the PGCD of the relative integers 9 p +4 and 2 p − 1 as a function of the values of p . E.5305 Let k be an element of Z . 1 Demonstrate that the integers 2 k +1 and 9 k +4 are prime to each other. 2 a Demonstrate that the PGCD of the integers 2 k − 1 and 9 k +4 is necessarily 1 or 17 . b Establish the following statement : pgcd (2 k − 1 ; 9 k +4) = 17 ⇐⇒ k ≡ 9 ( mod. 17) E.8823 Consider the sequence F n de Fibonacci defined by: F 0 =0 ; F 1 =1 ; F n +2 = F n +1 + F n for all n =2 Show that for any natural number n greater than or equal to 2 , the numbers F n +1 and F n are prime to each other. 8. Homogeneity property of PGCD https://chingmath.fr chapExoCorrec/3715 sacados/3715 Extrait de Metropole Septembre 2009 chapExoCorrec/6021 sacados/6021 chapExoCorrec/6076 sacados/6076 chapExoCorrec/4272 sacados/4272 Extrait de Extrait d'Amerique du Sud Novembre 2010 chapExoCorrec/3722 sacados/3722 chapExoCorrec/3720 sacados/3720 France Juin 1999 chapExoCorrec/5300 sacados/5300 Extrait Bac C Juin 1981 chapExoCorrec/5729 sacados/5729 chapExoCorrec/6025 sacados/6025 Poitier Juin 1982 chapExoCorrec/5305 sacados/5305 Bac C - Lyon Septembre 1979 chapExoCorrec/8823 sacados/8823 A finaliser la correction
ABCxyx E.5297 Proposition: (homogeneity property) For any non-zero relative numbers a , b , k , we have : pgcd ( k · a ; k · b ) = k · pgcd ( a ; b ) Let a and b be non-zero natural numbers such that : pgcd ( a ; b ) = d ; pgcd ( a + b ; ab ) = d Show that d is a divisor of d . E.6023 Let a and b be two natural numbers with a>b . Show equivalence : a b is irreducible ⇐⇒ a − b a · b is irreducible. 9. PGCD and set of common divisors E.12 Proposition: let a and b be two non-zero relative num-bers. The set of divisors common to a and b is the set of divisors of their PGCD. 1 Carry out the decomposition into prime factors of the following numbers : 27 × 90 ; 20 × 21 2 Determine the PGCD of the integers 2430 and 420. 3 Give the set of divisors common to these two integers. 10. Identity and Bézout’s Theorem E.4284 Proposition: (Bézout identity) Let a and b be two relative integers. If d is the PGCD of a and b then there exist two relative integers u and v such that : u · a + v · b = d Bézout’s theorem: Two relative integers a and b are prime to each other if, and only if, there exist two relative integers such that : u · a + v · b = 1 Using Bézout’s theorem, show that the pairs below define a pair of integers prime to each other : a (10 ; 3) b (15 ; 11) c (5 ; 17) E.6926 Consider the diophantine equation x 2 − 8 · y 2 =1 où x and y denote two relative integers. 1 Give two pairs of natural numbers less than 10 that are solutions of ( E ) . 2 Demonstrate that, if a pair of non-zero integers ( x ; y ) is a solution of ( E ) , then the integers x and y are prime to each other. E.3776 Indicate whether the following proposition is true or false and give a justification for the answer chosen : For any non-zero natural number n , n and 2 n +1 are prime to each other. E.5303 Let n be a relative integer. We de-fine the value of the integers a and b as a function of that of n by: a =3 n − 1 ; b = − 2 n +1 Show that the integers a and b are prime to each other what-ever the value of the natural number n . E.3750 Let n be a relative integer. We de-fine the value of the integers a and b as a function of that of n by: a =6 n +1 ; b = 9 n + 1 Show that the integers a and b are prime to each other what-ever the value of the natural number n . E.5308 Establish that, whatever the value of n , the two integers n +3 and − 2 n 2 − n +14 are prime to each other. E.4291 Indicate whether the following statement is true or false : ˇ If there are two relative integers u and v such that a · u + b · v =2 then the PGCD of a and b is equal to 2 . ı E.9480 Consider the triangle ABC right-angled B , shown below, such that BC = AB +2 and its mea-sures are integers : We model the situation by noting AB = x and AC = y . 1 a Express y 2 in terms of x as an expanded and reduced expression. b Deduce that the integer y is even. 2 a Justify that 2 · x 2 +4 · x +4 is a multiple of 4 . b Deduce that the integer x is even. 3 Complete the algorithm below giving us the values of x and y (with y< 1000 ) realizing the dimensions of this triangle: import math for x in range(...): y=math.sqrt(...) if math.floor(...)==...: print(x,y) https://chingmath.fr chapExoCorrec/5297 sacados/5297 chapExoCorrec/6023 sacados/6023 Extrait de Maroc Juin 1967 chapExoCorrec/12 sacados/12 chapExoCorrec/4284 sacados/4284 chapExoCorrec/6926 sacados/6926 Extrait d'Asie Juin 2015 chapExoCorrec/3776 sacados/3776 chapExoCorrec/5303 sacados/5303 chapExoCorrec/3750 sacados/3750 chapExoCorrec/5308 sacados/5308 chapExoCorrec/4291 sacados/4291 Extrait de Liban Juin 2007 chapExoCorrec/9480 sacados/9480 DE moi mais adapter l'exercice pour qu'il puisse montrer que seul 2 peut etre le pgcd de x et de y ABCxyx
11. Application of Bezout’s theorem E.6927 For each letter of the alpha-bet, use the table below to assign an integer between 0 and 25 : A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 A coding process is defined as follows : Step 1: to the letter we want to code, we associate the corresponding integer x in the table above. Step 2: we calculate the integer x defined by the rela-tions : x ≡ 9 · x + 2 ( mod. 26) ; 0 x 25 Step 3: to the integer x , we associate the corresponding letter in the table. 1 Demonstrate that the letter V is encoded by the letter J . 2 Quote the theorem that asserts the existence of two rela-tive integers u and v such that 9 · u +26 · v =1 . Give with-out justification a suitable pair ( u ; v ) . 3 Demonstrate that : x ≡ 9 · x +2 ( mod. 26) equals x ≡ 3 · x +20 ( mod. 26) 4 Decode the letter R . E.3772 For any natural number n greater than or equal to 2 , we pose : A ( n ) = n 4 + 1 1 Study the parity of the integer A (11) . 2 Show that, whatever the integer n , A ( n ) is not a multiple of 3 . 3 Show that any integer d divisor of A ( n ) is prime with n . 4 Show that, for any integer d divisor of A ( n ) : n 8 ≡ 1 ( mod. d ) E.6024 Let n be a natural integer, we pose : a = 2 n + 8 ; b = 3 n + 15 Let d be the PGCD of a and b . 1 Demonstrate that, for any n ∈ N , d divides 6 . 2 Consider the set S of natural integers n for which d =6 . That is, the set S is defined by: S = n ∈ N ⏐ ⏐ ⏐ pgcd (2 n +8 ; 3 n +15)=6 a Show that if n ∈S then there exists an integer k such that : n = − 4+3 · k . b Deduce the set S . E.5828 We pose : u =2+ 3 et v =2 − 3 1 Demonstrate by recurrence that, n denoting a positive integer, we can write: u n = a n + b n · 3 ; v n = a n − b n · 3 où a n and b n are positive integers. Express a n +1 and b n +1 in terms of a n and b n . 2 Establish the equalities: a n 2 − 3 · b n 2 = 1 ; a n · b n +1 − a n +1 · b n = 1 Deduce that the fractions a n b n , a n +1 a n , b n +1 b n sont irré-ductibles. E.3261 We denote by p a prime inte-ger greater than or equal to 7. The aim of the exercise is to show that the natural number n = p 4 − 1 is divisible by 240 , and then to apply this result. 1 Show that p is congruent to − 1 or to 1 modulo 3 Deduce that n is divisible by 3 . 2 Noting that p is odd, prove that there exists a natural number k such that p 2 − 1=4 · k · ( k +1) , then that n is di-visible by 16 . 3 Considering all possible remainders of the Euclidean di-vision of p by 5 , show that 5 divides n . 4 a Let a , b and c be three natural numbers. Show that if a divides c and b divides c , with a and b prime to each other, then ab divides c . b Deduce from the above that 240 divides n . 5 Are there fifteen prime integers p 1 , p 2 ,. . . , p 15 greater than or equal to 7 such that the integer: A = p 1 4 + p 2 4 + ··· + p 15 4 is a prime integer? 12. Gauss’s theorem E.8615 Gauss’s theorem: Let a , b , n be three non-zero relatfied integers such that n divides a · b . If n is prime with a then it divides b . Determine the set of pairs ( x ; y ) ∈ Z 2 solutions of the equa- tion : 12 · x = 13 · y https://chingmath.fr chapExoCorrec/6927 sacados/6927 Extrait d'Antilles-Guyanne Juin 2015 chapExoCorrec/3772 sacados/3772 chapExoCorrec/6024 sacados/6024 Montpellier Juin 1980 3 points chapExoCorrec/5828 sacados/5828 Bac Madagascar Septembre 1969 chapExoCorrec/3261 sacados/3261 chapExoCorrec/8615 sacados/8615
E.4285 Let a and b be two relative integers. 1 Show that if a · b ≡ 0 ( mod. 47) then a ≡ 0 ( mod. 47) or b ≡ 0 ( mod. 47) 2 Deduce that if a 2 ≡ 1 ( mod. 47) then a ≡ 1 ( mod. 47) or a ≡ − 1 ( mod. 47) E.3573 Consider the congruence sys-tem : ( S ) : n ≡ 2 ( mod. 3) n ≡ 1 ( mod. 5) où n denotes a relative integer. 1 Show that 11 is a solution of ( S ) . 2 Show that if n is solution of ( S ) then n − 11 is divisible by 3 . 3 Show that the solutions of ( S ) are all integers of the form 11+15 · k , où k denotes a relative integer. E.5299 Consider the equation ( E ) de-fined by: ( E ) : 17 x − 15 y = 3 où the resolution set is the set of pairs ( x ; y ) of relative inte-gers. Show that, for any couple ( x ; y ) solution of ( E ) , x is a multi-ple of 3 . E.3791 Let x and y be two integers verifying the equality: y · y − x = x · 2 − x It is assumed that the integer x is a prime integer. 1 Demonstrate that the integer x divides y . 2 We pose y = k · x with k ∈ Z : a Show that x divides 2 , then that x =2 . b Deduce the possible values of k . E.3718 Indicate whether the following statement is true or false and give reasons for your answer: Let N be a natural number whose writing in base 10 is aba 7 10 If N is divisible by 7 then a + b is divisible 7 . E.3775 Let ( E ) be the set of natural integers written, in base 10, in the form abba où a is a digit greater than or equal to 2 and b is any digit. Examples of ( E ) elements : 2002 ; 3773 ; 9119 . 1 Show that : ˇ n is divisible by 3 is equivalent to a + b is divisible by 3 ı 2 Show that : ˇ n is divisible by 7 is equivalent to b is divisible by 7 ı E.3716 We propose to study pairs ( a ; b ) of strictly positive integers, such as : a 2 = b 3 Let ( a ; b ) be such a pair. Let d = pgcd ( a ; b ) and u , v be the two natural numbers verifying: a = d · u ; b = d · v . 1 Show that : u 2 = d · v 3 . 2 Deduce that v divides u , then that v =1 . 3 Let ( a ; b ) be a pair of strictly positive integers. Show that we have a 2 = b 3 if, and only if, a and b are respectively the cube and square of the same integer. E.5298 We wish to determine the set of couples ( a ; b ) of natural numbers solutions of the equation : a 2 − 3 · a · b + b 2 = 0 We assume the existence of a couple ( a ; b ) solution of this equation : 1 Justify the existence of natural integers a and b prime to each other verifying the equality: a 2 − 3 · a · b + b 2 = 0 2 Show that a divides b 2 , then that a divides b . 3 Establish that b verifies the relationship : 1 − 3 b + b 2 = 0 . 4 Conclude. E.4273 Let ( x ; y ; z ) be a triplet solu-tion of the following two equations : z = ( x − y ) 2 ; z = x · y 1 Show that if x =0 , then the triplet ( x ; y ; z ) has value 0 ; 0 ; 0 . 2 It is now assumed that the integer x is non-zero. a Show that the integers x , y , z verify: x 2 − 3 · x · y + y 2 = 0 Deduce that there are then natural integers x and y prime to each other such that : x 2 − 3 · x · y + y 2 = 0 b Show that x divides y 2 , then that x divides y . c Establish that y verifies the relation; 1 − 3 · y + y 2 =0 d Conclude. 13. Corollary A of Gauss’s theorem E.4281 Corollary : (from Gauss’s theorem) Let a , b , c be three non-zero relative integers such that a divides c and b divides c . If the integers a and b are prime to each other then the product a · b divides c . Consider the polynomial A = n 3 − 6 · n 2 − n +6 where n ∈ Z . 1 Establish factorization : A = n − 6 n − 1 n + 1 2 a Establish that for any relative integer n , the integer A is divisible by 2 . b Establish that for any relative integer n , the integer A is divisible by 3 . c Deduce that for any relative integer n , the integer A https://chingmath.fr chapExoCorrec/4285 sacados/4285 chapExoCorrec/3573 sacados/3573 Extrait de Antilles-Guyane Septembre 2008 chapExoCorrec/5299 sacados/5299 Extrait du Bac - Etranger Juin 1981 chapExoCorrec/3791 sacados/3791 Extrait d'Antilles-Guyane Septembre 2009 chapExoCorrec/3718 sacados/3718 chapExoCorrec/3775 sacados/3775 chapExoCorrec/3716 sacados/3716 chapExoCorrec/5298 sacados/5298 chapExoCorrec/4273 sacados/4273 chapExoCorrec/4281 sacados/4281
is divisible by 6 . E.8616 Consider the polynomial A = n 3 − 3 · n 2 + n − 6 where n ∈ Z . 1 Establish the factorization : A = n − 3 n 2 +2 2 Prove that the integer A is divisible by 6 for any n ∈ Z E.8618 For any natural number n , we define the integer a by: a = n · 2 n + 1 7 n + 1 1 Justify that the integer a is even. 2 Justify that the integer a is divisible by 6 . 14. Corollary B of Gauss’s theorem E.8617 Corollary : (from Gauss’s theorem) Let a , b , c be three non-zero integers. If a and b are prime to each other and if a and c are prime to each other then a is prime with the product b · c . This can be translated as : pgcd ( a ; b ) = 1 pgcd ( a ; c ) = 1 = ⇒ pgcd ( a ; b · c ) = 1 Consider the polynomial 6 · n 3 − 7 · n 2 − 5 · x +1 where n ∈ Z . 1 Establish factorization : A = 6 · n − 1 n 2 − n − 1 2 Establish that for any relative integer n , the integer A is not divisible by 6 . 15. Corollary C of Gauss’s theorem E.3595 Corollary : (from Gauss’s theorem ) Let a , b , c be three non-zero integers such that p is a prime integer. If p divides the product a · b alors p divides a ou p divides b . Let a and b be two relative integers. 1 Show that : If a · b ≡ 0 ( mod. 47) then a ≡ 0 ( mod. 47) ou b ≡ 0 ( mod. 47) . 2 Deduce that : If a 2 ≡ 1 ( mod. 47) then a ≡ 1 ( mod. 47) ou a ≡ − 1 ( mod. 47) . E.4324 Consider the equation : ( F ) : 11 · x 2 − 7 · y 2 = 5 où x and y are relative integers. 1 a Demonstrate that if the couple ( x ; y ) is solution of ( F ) , then : x 2 ≡ 2 · y 2 ( mod. 5) b Let x and y be relative integers. Copy and complete the following two tables : Modulo 5 , x is congruent to 0 1 2 3 4 Modulo 5 , x 2 is congruent to Modulo 5 , y is congruent to 0 1 2 3 4 Modulo 5 , 2 y 2 is congruent to What are the possible values of the remainder of the Euclidean division of x 2 and 2 · y 2 by 5 ? c Deduce that if the couple ( x ; y ) is solution of ( F ) , then x and y are multiples of 5 . 2 Demonstrate that if x and y are multiples of 5 , then the pair ( x ; y ) is not a solution of ( F ) . What can we deduce from this for the equation ( F ) ? https://chingmath.fr chapExoCorrec/8616 sacados/8616 chapExoCorrec/8618 sacados/8618 chapExoCorrec/8617 sacados/8617 chapExoCorrec/3595 sacados/3595 chapExoCorrec/4324 sacados/4324 Extrait d'Antilles Juin 2011
E.4306 Consider the equation ( E ) on triplets ( x ; y ; z ) defined by: x 2 + y 2 = 5 2 · z 2 Consider a triplet ( x ; y ; z ) of relative integers verifying the equation ( E ) : 1 Check that the triplet A 1 ; 3 ; 2 is solution of ( E ) . 2 Demonstrate that z is divisible by 2 and x 2 + y 2 is divisi-ble by 10 . 3 Suppose y =3 , then show the following equivalence : x 2 ≡ 1 ( mod. 10) 4 Determine an integer-valued triplet ( x ; y ; z ) solutions of ( E ) où y is an odd integer. E.6019 Let a and b be two natural numbers whose sum and product have PGCD the square of a prime integer p . 1 Show that p 2 divides a 2 . (note that a 2 = a · ( a + b ) − a · b ) . Deduce that p divides a . Show that p divides b . 2 Show that the PGCD of a and b is either p or p 2 . E.5286 Let a and b be non-zero nat-ural numbers such that : pgcd ( a + b ; ab ) = p où p is a prime integer. 1 Show that p divides a 2 . (Note that : a 2 = a ( a + b ) − ab ) 2 Deduce that p divides a . We therefore find, similarly, that p divides b . 3 Demonstrate that : pgcd ( a ; b ) = p . 16. Bezout and Gauss theorems E.5304 1 Determine the set U of relative integers n such that n +2 divides 2 n − 1 . 2 Show that for any relative integer, the integers n +2 and 2 n 2 +3 n − 1 are prime to each other. 3 Determine the set V of relative integers n = − 2 such that (2 n − 1)(2 n 2 +3 n − 1) ( n 2 − 2)( n +2) is a relative integer. E.4058 Let p be a natural number greater than or equal to 2 and a be a non-zero natural number such that a and p are prime to each other : 1 Using reasoning by recurrence, show that for any non-zero integer n , the integers a n and p are prime to each other. 2 Establish the existence of a non-zero natural integer n such that : a n ≡ 1 ( mod. p ) 17. Diophantine equation E.6098 1 Demonstrate that the pair ( − 2 ; 17) is a solution of the equation : 12 x +31 y =503 2 En deduce that : If a pair of relative integers ( x ; y ) is a solution of the equation 12 x +31 y =503 then the pair veri-fies the relation 12 · x +2 =31 · 17 − y 3 Determine the set of all pairs of integers ( x ; y ) solutions of the equation : 12 x +31 y =503 E.6929 Consider the equation : 51 · x − 26 · y =1 où x and y are relative integers. 1 Justify, by stating a theorem from the course, that this equation admits at least one pair of solutions. 2 a Give a solution pair x 0 ; y 0 of this equation. b Determine the set of solution pairs for this equation. E.3752 Consider the equation ( E ) defined by: ( E ) : − 7 · x + 25 · y = 1 1 Determine a trivial pair ( x ; y ) of integers solution of the equation ( E ) . 2 Deduce the set of integer solutions of this equation ( E ) . E.3790 Consider the equation ( E ): 7 x − 6 y =1 où x and y are natural numbers. 1 Give a particular solution of the equation ( E ) . 2 Determine the set of pairs of natural numbers that are solutions of the equation ( E ) . E.4276 Consider the equation ( E ): 7 · x − 6 · y =1 où x and y are natural numbers. 1 Give a particular solution of the equation ( E ) . 2 Determine the set of pairs of natural numbers that are solutions of the equation ( E ) . E.8619 Consider the equation ( E ) defined by ( E ) : 135 · x + 18 · y = 9 1 Determine a trivial pair ( x ; y ) of integers solutions of the equation ( E ) . 2 Deduce the set of integer solutions of the equation ( E ) . E.4308 Determine the set of couples ( x ; y ) , où x and y are two relative integers, solutions of the equation : ( E ) : 2 · x + 11 · y = 7 https://chingmath.fr chapExoCorrec/4306 sacados/4306 chapExoCorrec/6019 sacados/6019 chapExoCorrec/5286 sacados/5286 Extrait Antilles-Guyanne Septembre 2001 chapExoCorrec/5304 sacados/5304 Bac C - Reims Juin 1982 4 points chapExoCorrec/4058 sacados/4058 chapExoCorrec/6098 sacados/6098 chapExoCorrec/6929 sacados/6929 Extrait d'Antilles-Guyane Septembre 2015 chapExoCorrec/3752 sacados/3752 chapExoCorrec/3790 sacados/3790 chapExoCorrec/4276 sacados/4276 chapExoCorrec/8619 sacados/8619 chapExoCorrec/4308 sacados/4308
E.6931 Consider the following equa-tion with unknowns x and y relative integers : ( E ): 7 x − 3 y = 1 An incomplete algorithm is given below. Its purpose is, when executed step by step, to recover the values taken by the vari-ables a and b which form solution pairs of the equation ( E ) où ( a ; b) is a pair of solution integers such that : − 5 a 10 ; − 5 B 10 . For X varying from − 5 to 10 (1) ... (2) ... Alors ( a ; b) ← ( X ; Y) End If End For End For E.3476 Questions 1 and 2 are indepen-dent. Let n be a non-zero natural number. 1 Consider the equation noted ( E ) : 3 x + 7 y = 10 2 n x and y are relative integers. a Determine a pair ( u ; v ) of relative integers such that : 3 u + 7 v = 1 . Deduce a particular solution ( u 0 ; v 0 ) of the equation ( E ) . b Determine the set of pairs of relative integers ( x ; y ) solutions of ( E ) . 2 Consider the equation noted ( G ) : 3 x 2 + 7 y 2 = 10 2 n où x and y are relative integers. a Show that : 100 ≡ 2 ( mod. 7) . Show that if ( x ; y ) is a solution of ( G ) then : 3 x 2 ≡ 2 n ( mod. 7) b Reproduce and complete the following table : Reste from division euclidienne of x by 7 0 1 2 3 4 5 6 Reste of the division euclidienne of 3 x 2 by 7 c Demonstrate that 2 n is congruent to 1 , 2 or 4 modulo 7 . Deduce that the equation ( G ) admits no solution. 18. Courses E.3384 Let a , b and c be three natural integers. Show that if a divides c and b divides c , with a and b prime to each other, then a · b divides c . E.6248 The aim of this section is to demonstrate that the set of prime integers is infinite by reasoning through the absurd. 1 It is assumed that there exists a finite number of prime integers denoted p 1 , p 2 , . . . , p n . Consider the integer E product of all prime integers in-creased by 1 : E = p 1 × p 2 × · · · × p n + 1 Show that E is an integer greater than or equal to 2 , and that E is prime with each of the integers p 1 , p 2 , . . . , p n . 2 Using the fact that E admits a prime divisor, conclude. E.6923 We denote by a , b and c three non-zero natural numbers such that : pgcd ( b ; c )=1 Prove, using Gauss’s theorem, that : ˇSi b divides a and c divides a then the product b · c divides a ı 19. Unclassified financial years E.6930 For each of the following five statements, indicate whether it is true or false and justify your answer. One point is awarded for each correct answer that is prop-erly justified. An answer without justification will not be counted. No points will be deducted for not answering a question. Statement 1 For any natural number n , the units digit of n 2 + n is never equal to 4 . Consider the sequence u defined, for n 1 , by: u n = 1 n · pgcd (20 ; n ) Proposition 2 : the sequence u n is convergent. https://chingmath.fr chapExoCorrec/6931 sacados/6931 Extrait Antilles-Guyane Juin 2016 chapExoCorrec/3476 sacados/3476 chapExoCorrec/3384 sacados/3384 chapExoCorrec/6248 sacados/6248 Extrait d'Asie Juin 2014 chapExoCorrec/6923 sacados/6923 chapExoCorrec/6930 sacados/6930