Grade 12 - Exp. / Congruences 56 exercises (100% corrected)

a
1. Congruence E.3402 Definition: Let a and b be two relative integers ( a; b ∈ Z ) and c a non-zero natural integer ( c ∈ N ∗ ) : a ≡ b ( mod. c ) ⇐⇒ ( a − b ) multiple of c . Check the validity of each of the following equalities: a 15 ≡ 27 ( mod. 3) b 17 ≡ 11 ( mod. 4) c 153 ≡ 237 ( mod. 12) d − 5 ≡ 8 ( mod. 13) e − 81 ≡ 224 ( mod. 6) f 37 4 ≡ 1 ( mod. 4) E.3365 1 Determine a value of the integer a ∈ 10 ; 20 for which the equality is true : a 25 ≡ a ( mod. 4) b 37 ≡ a ( mod. 10) c 52 ≡ a ( mod. 7) d 5 ≡ a ( mod. 14) e 1 ≡ a ( mod. 9) f 13 ≡ a ( mod. 5) 2 Determine a value of n for which equality is true : a 21 ≡ 1 ( mod. n ) b 14 ≡ 4 ( mod. n ) c 9 ≡ 14 ( mod. n ) d 10 ≡ 25 ( mod. n ) E.4283 1 Determine the remainder in the Euclidean division of 2 009 by 11 . 2 Determine the remainder in the Euclidean division of 2 10 by 11 . 3 Determine the remainder in the Euclidean division of 2 2009 + 2009 by 11 . 2. Operations on congruences E.5826 Use congruences to calculate the remainders of Euclidean division by 7 of the following integers : a 5 6 b 5 6 p ; pour p ∈ N ∗ c 33 38 E.4286 1 Determine the remainder of the Euclidean division of 2 009 2 by 16 . 2 Deduce that 2009 8001 ≡ 2009 ( mod. 16) E.3417 For each of the following propositions, indicate whether it is true or false and give a demonstration of the chosen answer. An unproven answer scores no points. For any non-zero natural number n : ˇ 5 6 n +1 + 2 3 n +1 is divisible by 5 ı? ˇ 5 6 n +1 + 2 3 n +1 is divisible by 7 ı? E.4290 For any natural number a , show that : if a 17 ≡ b ( mod. 55) and if a 40 ≡ 1 ( mod. 55) then b 33 ≡ a ( mod. 55) 3. Congruence operations and problems E.3406 In this exercise we study the divisibility by 11 by exploiting the congruence modulo 11 of the powers of 10 1 a Check that : 100 ≡ 1 ( mod. 11) . Deduce that : 10 4 ≡ 1 ( mod. 11) . b Check that : 10 ≡ − 1 ( mod. 11) . Deduce that : 10 3 ≡ − 1 ( mod. 11) 10 5 ≡ − 1 ( mod. 11) 2 a Using the equality 3729=37 × 100+29 and the previ-ous results, show that 3729 is divisible by 11 . b Using the previous method, investigate the divisibility of 9240 by 11 . 3 a Using equality: 3729 = 3 × 1000 + 7 × 100 + 2 × 10 + 9 and the previous results, show that 3729 is divisible by 11 . b Using this method, study the divisibility of 9240 by 11 . 4 Study the divisibility of 197 277 by 11 . https://chingmath.fr chapExoCorrec/3402 sacados/3402 chapExoCorrec/3365 sacados/3365 chapExoCorrec/4283 sacados/4283 Extrait de Metropole Septembre 2009 chapExoCorrec/5826 sacados/5826 Bac Montpellier Juin 1970 chapExoCorrec/4286 sacados/4286 Extrait de Liban Juin 2009 chapExoCorrec/3417 sacados/3417 Extrait de Liban Juin 2008 chapExoCorrec/4290 sacados/4290 chapExoCorrec/3406 sacados/3406 Term L Japon Juin 2003
E.3468 Consider the integers : A = 8 387 592 115 ; B = 9 276 312 516 1 a Show that 1 000 is divisible by 8 . b Show that A is congruent to 3 modulo 8 . c Give the natural number b strictly less than 8 such that B is congruent to b modulo 8 . 2 Determine the natural numbers strictly less than 8 that are congruent to A + B and A · B respectively 3 a Show that B 2 is divisible by 8 . b Show that A 2 is not divisible by 8 . c Show that A 100 is not divisible by 8 . E.6804 Consider the Mersenne inte-ger 2 33 − 1 . A student uses his calculator and obtains the results below. 2 33 − 1 ÷ 3 2863311530 2 33 − 1 ÷ 4 2147483648 2 33 − 1 ÷ 12 715827882.6 He states that 3 divides 2 33 − 1 and 4 divides 2 33 − 1 and 12 does not divide 2 33 − 1 . 1 Justify that, in reality, 4 does not divide 2 33 − 1 . 2 Noting that 2 ≡− 1 ( mod. 3) , show that, in reality, 3 , does not divide 2 33 − 1 . 3 Calculate the sum : S =1+2 3 + 2 3 2 + 2 3 3 + ··· + 2 3 10 4 Deduce that 7 divides 2 33 − 1 . 4. Congruence and expression E.3388 Show that, for any natural number n , 4 n is congruent to 1 modulo 3 . E.4274 Consider the sequence u n defined for any non-zero natural number n by: u n =2 n +3 n + 6 n − 1 1 Calculate the first six terms of the sequence. 2 Show that, for any non-zero natural number n , u n is even. 3 Show that, for any non-zero even natural number n , u n is divisible by 4 . E.3632 1 Show that for any natural integer n , 3 divides the integer 2 2 n − 1 . 2 Let p be a natural integer. Show that of the integers p , p +10 , p +20 , one and only one of them is divisible by 3. E.3598 Let n be a relative integer. In-dicate whether the following proposition is true or false and give a justification for the answer chosen : n 2 + n +3 ≡ 0 ( mod. 5) if, and only if, n ≡ 1 ( mod. 5) . E.3405 1 a Show that 1999 is congruent to 4 modulo 7 . b Determine the smallest natural integer congruent to 2007 modulo 7 . 2 Let n be a natural number congruent to 5 modulo 7 . a Determine a natural number congruent to n 3 modulo 7 . b Deduce that ( n 3 +1) is divisible by 7 . 3 Show that if n is a natural number congruent to 4 modulo 7 then ( n 3 − 1) is divisible by 7 . 4 Consider the integer: A =1999 3 +2007 3 . Without calculating A , show using the previous results that A is divisible by 7 . E.4287 Let a and b be two natural numbers less than or equal to 9 with a =0 . Consider the number N = a × 10 3 + b . Recall that in base 10 this number is written in the form : N = a 00 b We propose to determine which of these natural numbers N are divisible by 7 . 1 Check that : 10 3 ≡− 1 ( mod. 7) 2 Deduce all the integers N sought. E.6925 Let p , q , r be three relative integers verifying: − 3 p + q + 2 r ≡ 0 ( mod. 6) 3 p − 3 q ≡ 0 ( mod. 6) 6 p + 2 q − 2 r ≡ 0 ( mod. 6) Deduce that these integers verify the system : q − r ≡ 0 ( mod. 3) p − q ≡ 0 ( mod. 2) 5. Studying the remains of an expression E.3493 Let n be a natural number. 1 Expand ( n +3) 4 . 2 Show that : ( n + 3) 4 ≡ n 4 + 2 n 2 + 1 ( mod. 4) 3 Study the divisibility of ( n +3) 4 by 4 according to the remainder of the Euclidean division of n by 4. https://chingmath.fr chapExoCorrec/3468 sacados/3468 chapExoCorrec/6804 sacados/6804 chapExoCorrec/3388 sacados/3388 chapExoCorrec/4274 sacados/4274 chapExoCorrec/3632 sacados/3632 chapExoCorrec/3598 sacados/3598 chapExoCorrec/3405 sacados/3405 Term L Antille-guyane Juin 2002 chapExoCorrec/4287 sacados/4287 Extrait de Metropole Juin 2009 chapExoCorrec/6925 sacados/6925 chapExoCorrec/3493 sacados/3493
E.5830 1 Study, according to the values of the natural integer n , the remainder of the division by 7 of the integer: A = n 2 − n +1 2 Deduce the integers n such that the integer A is divisible by 7 . 3 Determine the remainder of the division by 7 of the inte-ger: B = 2 753 2 − 2 753 + 1 E.4278 Consider the equation ( E ) : x 2 + y 2 ≡ 0 ( mod. 3) où ( x ; y ) is a pair of relative integers. Establish that if a pair is a solution of the equation ( E ) then it is a pair of multiples of 3 . E.3278 In this question, x and y denote natural integers. 1 What are the possible remainders of the Euclidean divi-sion of x 2 by 7 ? 2 Demonstrate that 7 divides x 2 + y 2 if, and only if, 7 di-vides x and 7 divides y . 6. Equations E.3404 1 a For any n ∈ N , let a be the remainder of the Eu-clidean division of 8 n by 5; complete the following table : n 0 1 2 3 4 a b Show that, in Z , the equation 8 n ≡ 4 ( mod. 5) admits as solution set all relative integers whose remainder by Euclidean division by 5 is 3 . Let’s note this set : S = 3+5 · k ⏐ ⏐ k ∈ Z 2 Establish that the equation 5 n ≡ 2 ( mod. 6) admits in Z for solution set : S = 4+6 · k ⏐ ⏐ k ∈ Z 3 In Z , justify that the equation 6 n ≡ 5 ( mod. 4) admits no solution. E.5455 Let x be a relative integer. By studying the possible remainders of the Euclidean division of x by 6 , solve in Z the following equations : a 5 · x ≡ 2 ( mod. 6) b 2 · x ≡ 3 ( mod. 6) E.8611 Let x be a relative integer. By studying the possible remainders of the Euclidean division of an integer x by 7 , solve in Z the following equations : a 4 · x ≡ 1 ( mod. 7) b 6 · x ≡ 3 ( mod. 7) E.3599 Consider the set : A 7 = 1 ; 2 ; 3 ; 4 ; 5 ; 6 1 For any element a of A 7 , write in the table below the unique element y of A 7 such that : a · y ≡ 1 ( mod. 7) . a 1 2 3 4 5 6 y 6 2 For x relative integer, show that the equation : 3 x ≡ 5 ( mod. 7) equals x ≡ 4 ( mod. 7) . 3 Let a be an element of A 7 , show that the only relative integers x solutions of the equation a · x ≡ 0 ( mod. 7) are multiples of 7 . 7. Powers congruent to 0 E.5454 1 Determine the smallest value of the natural number n achieving congruence : 6 n ≡ 0 ( mod. 8) 2 For any natural integer n , determine the value of the remainder of the integer A defined below by Euclidean division by 8 : A =6 n +9 n E.5453 1 Determine the smallest integer k achieving equivalence : 6 k ≡ 0 ( mod. 4) 2 For any natural number a , using reasoning by recurrence, establish the congruence below for any non-zero natural number n : ( a + 6) n ≡ a n + 6 · n · a n − 1 ( mod. 4) E.3492 In the exercise, n represents a natu-ral number. 1 a Study the remainder of the Euclidean division of 2 n by the Euclidean division by 4 as a function of the values of n . b Study the remainder of the Euclidean division of 3 n by the Euclidean division by 4 as a function of the values of n . Hint : we will perform a case disjunction on the parity of n . 2 Deduce, as a function of n , the remainder, by Euclidean division by 4, of the sum : 1 n + 2 n + 3 n + 4 n + 5 n 8. Cyclic powers https://chingmath.fr chapExoCorrec/5830 sacados/5830 Bac Cambodge et Laos Juin 1968 chapExoCorrec/4278 sacados/4278 Extrait de Liban Juin 2010 chapExoCorrec/3278 sacados/3278 chapExoCorrec/3404 sacados/3404 chapExoCorrec/5455 sacados/5455 chapExoCorrec/8611 sacados/8611 chapExoCorrec/3599 sacados/3599 chapExoCorrec/5454 sacados/5454 chapExoCorrec/5453 sacados/5453 chapExoCorrec/3492 sacados/3492
E.3403 1 Complete the table below où r n represents the remainder of the Euclidean division of 7 n by 4: n 0 1 2 3 4 5 r n 2 Deduce the remainder of the Euclidean division of 7 235 by 4. E.8612 1 Complete the table below où r n represents the remainder of the Euclidean division of 12 n by 5: n 0 1 2 3 4 5 r n 2 Establish that the integer 12 39 − 3 is divisible by 5 . E.5037 1 Complete the following table of values : n 0 1 2 3 4 3 n Rest of 3 n par 5 2 Justify that for any natural number n , we have : 2008 4 · n ≡ 1 ( mod. 5) 3 Deduce that 2008 2008 − 31 is divisible by 5 . E.3571 1 Determine the remainder in the Euclidean division of 2 009 by 11. 2 Determine the remainder in the Euclidean division of 2 10 by 11. 3 Determine the remainder in the Euclidean division of 2 2 009 +2 009 by 11. E.3408 1 a Determine the remainders of the Euclidean division by 7 of the integers 3 n for n ∈ N où n 6 . The following table will be completed : Puissance de 3 3 0 3 1 3 2 3 3 3 4 3 5 3 6 Remainder modulo 7 b Deduce that, for any k ∈ N , 3 6 k is congruent to 1 mod-ulo 7 . 2 a Determine the smallest natural integer congruent to 1515 modulo 7 . b After noticing that 2004=6 × 334 , deduce from ques-tion 1 the remainder of the Euclidean division of 1515 2004 by 7 . c Show that in the Euclidean division of 1515 2006 by 7 , the remainder is 2 . E.8613 Determine the remainder of the Eu-clidean division of 17 159 541 by 7. Hint: we will use congruence : 2 3 ≡ 1 ( mod. 7) E.3491 1 We are interested, for any natural number n , in the re-mainder of the Euclidean division of 2 n by 7. a Complete the following table : n 0 1 2 3 4 Reste from division de 2 n per 7 b We note r the remainder of the Euclidean division of n by 3 ; justify the following equality: 2 n ≡ 2 r ( mod. 7) 2 a Deduce that for any natural number k , the integer 2 3 · k − 1 is a multiple of 7. b Show that for any natural number k , the integer 2 3 · k +1 − 2 is a multiple of 7. E.3489 1 a Determine the remainder of the Euclidean division of 10 3 by 27 . b Deduce the remainder of the Euclidean division by 27 of the following integer: A =345 948 546 421 2 Determine the remainder of the Euclidean division by 16 of the following nomre : B =15 × 33 51 − 9 × 18 152 +15 37 E.3553 Let n be a natural number. 1 Find according to the values of n , the remainders of the division of 5 n by 13 . 2 Deduce that 1981 1981 − 5 is divisible by 13 . 3 Demonstrate that, for any natural number n greater than or equal to 1 , the integer N =31 4 n +1 +18 4 n − 1 is divisible by 13. E.4309 Consider the integer N =11 2011 . Show that the integer N is congruent to 4 modulo 7 . E.4282 For n a non-zero natural num-ber, consider the equation denoted ( G ) : 3 · x 2 +7 · y 2 =10 2 · n où x and y are relative integers. 1 Show that : 100 ≡ 2 ( mod. 7) Show that if ( x ; y ) is a solution of ( G ) then : 3 · x 2 ≡ 2 n ( mod. 7) . 2 Reproduce and complete the following table : Reste of the Euclidean division de x par 7 0 1 2 3 4 5 6 Reste of the Euclidean division de 3 · x 2 par 7 3 Demonstrate that 2 n is congruent to 1 , 2 , or 4 modulo 7 . Deduce that the equation ( G ) admits no solution. https://chingmath.fr chapExoCorrec/3403 sacados/3403 chapExoCorrec/8612 sacados/8612 chapExoCorrec/5037 sacados/5037 chapExoCorrec/3571 sacados/3571 Extrait de Metropole et Reunion Septembre 2009 chapExoCorrec/3408 sacados/3408 chapExoCorrec/8613 sacados/8613 chapExoCorrec/3491 sacados/3491 chapExoCorrec/3489 sacados/3489 chapExoCorrec/3553 sacados/3553 chapExoCorrec/4309 sacados/4309 chapExoCorrec/4282 sacados/4282 Extrait de Nouvelle-Caledonie Novembre 2009
E.4277 Consider the relationship : ( F ): 7 n − 3 × 2 m =1 1 We assume m 4 . Show that there are exactly two solu-tion pairs. 2 It is now assumed that m 5 . a Show that if the couple ( n ; m ) verifies the relation ( F ) then : 7 n ≡ 1 ( mod. 32) . b By studying the remainders of the division by 32 of the powers of 7 , show that ( n ; m ) verifies the relation ( F ) then n is divisible by 4 . c Deduce that if the pair ( n ; m ) verifies the relation ( F ) then 7 n ≡ 1 ( mod. 5) 9. Reasoning by recurrence E.3457 Show by reasoning through recur-rence that for any natural number n , the integer 5 n − 1 is a multiple of 4. E.3296 Show, using reasoning by recurrence, that for any natural number n , we have : 5 n +2 ≡ 25 ( mod. 100) E.3294 Consider the sequence u n of natural numbers defined by: u 0 = 14 ; u n +1 = 5 u n − 6 for any n ∈ N Show that, for any natural number n , u n +2 ≡ u n ( mod. 4) . E.3458 Consider the sequence u n of natural numbers defined by: u 0 = 14 ; u n +1 = 5 · u n − 6 for all n ∈ N 1 Show by recurrence that, for any natural number: 2 · u n = 5 n +2 + 3 2 a Justify that for any natural number n , 2 · u n is a mul-tiple of 4. b Show that for any natural number n , we have : 2 · u n ≡ 28 ( mod. 100) E.3596 Part A 1 Determine the remainder of the Euclidean division of 2 009 2 by 16 . 2 Deduce that : 2 009 8 001 ≡ 2 009 ( mod. 16) Part B Consider the sequence u n defined on N by u 0 =2 009 2 − 1 and, for any natural number n : u n +1 = u n +1 5 − 1 . 1 a Demonstrate that u 0 is divisible by 5 . b Demonstrate, using Newton’s binomial formula, that for any natural number n : u n +1 = u n · u 4 n + 5 · u 3 n + 2 · u 2 n + 2 · u n + 1 c Demonstrate by recurrence that, for any natural num-ber n , u n is divisible by 5 n +1 . 2 a Check that u 3 =2 009 250 − 1 then deduce that 2 009 250 ≡ 1 ( mod. 625) . b Then demonstrate that : 2 009 8 001 ≡ 2 009 ( mod. 625) 10. Writing integers in a base E.3407 A natural number N is written cabc in the base-five numeration system où a , b , c are non-zero, i.e.: N = c × 5 3 + a × 5 2 + b × 5 + c où a , b , c are integers such that : 0 <a < 5 ; 0 <b < 5 ; 0 <c < 5 This same integer N is written aba in the base-eight number-ing system. 1 Show that N =65 a +8 b and deduce that : 40 a = 126 c − 3 b . 2 a Justify that : 40 a ≡ 0 ( mod. 3) . Deduce the value of a . b Show that : b ≡ 0 ( mod. 2) . Determine the values of b and c . c Give the writing of the integer N in bases five, eight and ten. https://chingmath.fr chapExoCorrec/4277 sacados/4277 chapExoCorrec/3457 sacados/3457 chapExoCorrec/3296 sacados/3296 chapExoCorrec/3294 sacados/3294 chapExoCorrec/3458 sacados/3458 chapExoCorrec/3596 sacados/3596 Extrait de Liban Juin 2009 chapExoCorrec/3407 sacados/3407
E.3323 Part A : Course question What are the compatibility properties of the congruence rela-tion with addition, multiplication and powers? Demonstrate the compatibility property with multiplication. Part B We note 0 , 1 , 2 , . . . , 9 , ¸ , ˛ the digits of the writing of an integer in base 12. For example: ˛¸ 12 = ˛ × 12 2 + ¸ × 12 + 7 = 11 × 12 2 + 10 × 12 + 7 = 1711 en base 10 1 a Let N 1 be the integer written in base 12: N 1 = ˛ 1 ¸ 12 Determine the writing of N 1 in base 10. b Let N 2 be the integer written in base 10: N 2 = 1131 = 1 × 10 3 + 1 × 10 2 + 3 × 10 + 1 Determine the writing of N 2 in base 12. Throughout the sequel , a natural integer N will generally be written in base 12 : N = a n · · · a 1 a 0 12 2 a Demonstrate that N ≡ a 0 ( mod. 3) . Deduce a crite-rion for divisibility by 3 of an integer written in base 12. b Using its writing in base 12, determine whether N 2 is divisible by 3 . Confirm with its writing in base 10. 3 a Show that N ≡ a n + ··· + a 1 + a 0 ( mod. 11) . Deduce a criterion for divisibility by 11 of an integer written in base 12. b Using its writing in base 12, determine whether N 1 is divisible by 11. Confirm with its writing in base 10. 4 An integer N is written x 4 y 12 . Determine the values of x and y for which N is divisible by 33. 11. Courses E.3373 Reminder : For two relative integers a and b , we say that a is congruent to b modulo 7 , and we write a ≡ b ( mod. 7) when there exists a relative integer k such that a = b +7 k . This question constitutes an organized restatement of knowl-edge : 1 Let a , b , c , and d be relative integers. Prove that : Si a ≡ b ( mod. 7) et c ≡ d ( mod. 7) then a · c ≡ b · d ( mod. 7) . 2 Deduce that : for a and b non-zero relative integers. If a ≡ b ( mod. 7) then for any natural integer n , a n ≡ b n ( mod. 7) . E.738 Let p be a natural number greater than or equal to 2 and a be a non-zero natural number Show that if there exists a natural number n such that a n ≡ 0 ( mod. p ) then for any natural number k , we have the implication: k n = ⇒ a k ≡ 0 ( mod. p ) 12. Unclassified financial years E.1716 1 Determine the Euclidean division of 1038 by 17. 2 By studying the square (61 × 17+1) 2 , determine the re-mainder of the Euclidean division of 1038 2 by 17. 3 Deduce a conjecture about, for any natural number n , the Euclidean division of 1038 n by 17. E.3627 In this question, any trace of re-search, however incomplete, or initiative, however unsuccess-ful, will be taken into account in the assessment . Let a and b be two natural numbers less than or equal to 9 with a =0 . Consider the integer N = a × 10 3 + b . Recall that in base 10 this integer is written as : N = a 00 b We propose to determine which of these natural numbers N are divisible by 7 . 1 Check that : 10 3 ≡− 1 ( mod. 7) 2 Deduce all the integers N sought. E.5301 Consider the natural number A , written 1 x 416 in the base-seven numeration system. 1 Determine x so that : a A be divisible by six; b A be divisible by five. Deduce that there exists x such that A is divisible by thirty. 2 x is given the value zero. Determine the decimal form of A . What is the number of positive divisors of A ? What is the set of positive divisors of A that are prime with three? E.4289 1 What is the remainder of the Euclidean division of 6 10 by 11 ? Justify. 2 What is the remainder of the Euclidean division of 6 4 by 5 ? Justify. 3 Deduce that : 6 40 ≡ 1 ( mod. 11) and 6 40 ≡ 1 ( mod. 5) . 4 Demonstrate that 6 40 − 1 is divisible by 55 . https://chingmath.fr chapExoCorrec/3323 sacados/3323 chapExoCorrec/3373 sacados/3373 chapExoCorrec/738 sacados/738 chapExoCorrec/1716 sacados/1716 chapExoCorrec/3627 sacados/3627 chapExoCorrec/5301 sacados/5301 Bac C - Lyon Juin 1980 4 points chapExoCorrec/4289 sacados/4289
E.5038 1 Let n be a natural number. Express the remainder of the Euclidean division of n 2 by 8 in terms of the remainder of the Euclidean division of n by 4 . 2 Let a and b be two integers. Establish the following prop-erty: ˇSi a 2 + b 2 is an integer divisible by 8 then a and b are integers pairsı E.3717 For each of the following two propositions, indicate whether it is true or false and give a demonstration of the chosen answer. For any non-zero natural number n : 1 ˇ 5 6 n +1 +2 3 n +1 is divisible by 5 ı. 2 ˇ 5 6 n +1 +2 3 n +1 is divisible by 7 ı. E.6078 For each question, state whether the proposition is true or false : 1 For any natural number n , we have : 2 3 n − 1 ≡ 0 ( mod. 7) 2 Let x be a natural integer. If x 2 + x ≡ 0 ( mod. 12) then x ≡ 0 ( mod. 4) https://chingmath.fr chapExoCorrec/5038 sacados/5038 chapExoCorrec/3717 sacados/3717 Extrait de Liban Juin 2008 chapExoCorrec/6078 sacados/6078