Bachillerato 2 - Exp. / Anales sobre PGCD 35 ejercicios (incluyendo 32 corregidos)

a
1. PGCD, propiedad y congruencia E.5284 1 a Demuestre que 3 n 3 − 11 n +48 es divisible por n +3 para cualquier número natural n . b Demuestre que 3 n 2 − 9 n +16 es un número natural dis-tinto de cero para cualquier número natural n . 2 Demuestra que, para todos los números naturales distin-tos de cero a , b y c , la siguiente igualdad es cierta: pgcd ( a ; b ) = pgcd ( b · c − a ; b ) 3 Demuestre que, para cualquier número natural n , mayor o igual que 2 , se cumple la igualdad : pgcd (3 n 3 − 11 n ; n +3)= pgcd (48 ; n +3) 4 a Determina el conjunto de divisores enteros naturales de 48 . b Deducir el conjunto de números naturales n tales que 3 n 3 − 11 n n +3 es un número natural. E.5285 Las sucesiones de números natu-rales x n y y n se definen por: x 0 = 3 ; x n +1 = 2 · x n − 1 y 0 = 1 ; y n +1 = 2 · y n + 3 1 Demuestre por recurrencia que para cualquier número entero n ∈ N : x n = 2 n +1 + 1 2 a Calcular el PGCD de x 8 y x 9 , y luego el de x 2002 y x 2003 . ¾Qué se puede deducir para x 8 y x 9 , por un lado, y para x 2002 y x 2003 , por otro? b x n y x n +1 son primos entre sí para todo número natu-ral n ? 3 a Demuestra que para todo número natural n : 2 · x n − y n = 5 b Expresar y n en función de n . c Utilizando las congruencias módulo 5 , estudiar según los valores del entero natural p el resto de la división euclidiana de 2 p por 5 . d Se denota d n el PGCD de x n y de y n para todo número natural n . Demostrar que se tiene d n =1 o d n =5 ; deducir el con-junto de números naturales n tales que x n y y n son primos entre sí. E.3320 Consideremos la sucesión u n de números naturales definida por: u 0 = 14 u n +1 = 5 u n − 6 para todo número natural n 1 Calculemos u 1 , u 2 , u 3 y u 4 . ¾Qué conjetura se puede formular sobre los dos últimos dígitos de u n ? 2 Demuestre que, para todo número natural n : u n +2 ≡ u n ( mod. 4) . Deduzca que, para todo número natural k : u 2 k ≡ 2 ( mod. 4) et u 2 k +1 ≡ 0 ( mod. 4) . 3 a Demuestre por recurrencia que, para cualquier en-tero n ∈ N : 2 · u n = 5 n +2 + 3 . b Deduzca que, para todo número natural n : 2 u n ≡ 28 ( mod. 100) . 4 Determine los dos últimos dígitos de la escritura decimal de u n según los valores de n . 5 Demuestre que el PGCD de dos términos consecutivos de la sucesión u n es constante. Especifique su valor. E.3719 Parte A Se admite que 1 999 es un número primo. Determinar el con-junto de pares ( a ; b ) de números naturales que admiten como suma 11 994 y como PGCD 1 999 . Parte B Consideramos la ecuación ( E ) de incógnita n perteneciente a N : ( E ): n 2 − S · n +11 994=0 donde S es un número natu-ral. Nos interesan los valores de S tales que ( E ) admita dos solu-ciones en N . 1 ¾Se puede determinar un entero S tal que 3 sea solución de ( E ) ? Si es así, especifique la segunda solución. 2 ¾Se puede determinar un entero S tal que 5 sea solución de ( E ) ? 3 Demuestre que todo número entero n solución de ( E ) es un divisor de 11 994 . Deduzca todos los valores posibles de S tales que ( E ) admita dos soluciones enteras. Parte C Cómo se demostraría que 1 999 es un entero primo? Especifique el razonamiento utilizado? La lista de todos los enteros primos menores que 100 est es-pecificada a continuación : 2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 23 ; 31 ; 37 ; 41 ; 43 ; 47 ; 53 ; 59 61 ; 67 ; 71 ; 73 ; 79 ; 83 ; 89 ; 97 https://chingmath.fr chapExoCorrec/5284 sacados/5284 Asie Juin 2003 4 points chapExoCorrec/5285 sacados/5285 Liban Mai 2003 5 points chapExoCorrec/3320 sacados/3320 chapExoCorrec/3719 sacados/3719
E.3246 En este ejercicio, se puede utilizar la proposición : Proposición: ˇ Dados dos números naturales, a y b distin-tos de cero, si pgcd ( a ; b )=1 entonces pgcd ( a 2 ; b 2 )=1 ı Una sucesión ( S n ) se define para n> 0 mediante : S n = n p =1 p 3 . Se propone calcular, para todo número natural distinto de cero n , el máximo común divisor de S n y S n +1 . 1 Demostrar que, para todo n> 0 , se tiene : S n = n ( n +1) 2 2 . 2 Estudio del caso en el que n es par. Sea k el número natural distinto de cero tal que n =2 k . a Demostrar que : pgcd ( S 2 k ; S 2 k +1 ) = (2 k + 1) 2 · pgcd ( k 2 ; ( k +1) 2 ) . b Calcular: pgcd ( k ; k +1) . c Calcular: pgcd ( S 2 k ; S 2 k +1 ) . 3 Estudio del caso en el que n es impar. Sea k el número natural distinto de cero tal que n =2 k +1 . a Demostrar que los números enteros 2 k +1 y 2 k +3 son primos entre sí. b Calcular: pgcd ( S 2 k +1 ; S 2 k +2 ) . 4 Deduzca de las preguntas anteriores que existe un único valor de n , que se determinará, para el cual S n y S n +1 son primos entre sí. 2. Teorema de Bezout E.3226 En este ejercicio, a y b designan números enteros estrictamente positivos. 1 a Demuestre que si existen dos números enteros rela-tivos u y v tales que a · u + b · v =1 , entonces los números enteros a y b son primos entre sí. b Deduzca que si ( a 2 + a · b − b 2 ) 2 =1 , entonces a y b son primos entre sí. 2 Se propone determinar los pares de números enteros es-trictamente positivos ( a ; b ) tales que ( a 2 + a · b − b 2 ) 2 =1 . Dicho par se denominará solución. a Determinar a cuando : a = b . b Verificar que (1 ; 1) , (2 ; 3) y (5 ; 8) son tres soluciones particulares. c Demostrar que si ( a ; b ) es solución y si a<b , entonces : a 2 − b 2 < 0 . 3 a Demuestra que si ( x ; y ) es una solución diferente de (1 ; 1) , entonces ( y − x ; x ) y ( y ; y + x ) también son solu-ciones. b Deduce de 2 b tres nuevas soluciones. 4 Consideramos la sucesión de números enteros estricta-mente positivos a n n definida por a 0 = a 1 =1 y, para todo número entero n , n 0 : a n +2 = a n +1 + a n . Demuestre que para todo entero n 0 , ( a n ; a n +1 ) es solu-ción. Deduzca que los enteros a n y a n +1 son primos entre sí. E.3741 1 Demostrar que, para todo número natural distinto de cero k y para todo número natural x : ( x − 1) · 1 + x + x 2 + · · · + x k − 1 = x k − 1 En todo el resto del ejercicio, consideramos un entero a mayor o igual que 2 . 2 a Sea n un entero natural distinto de cero y d un divi-sor positivo de n : n = d · k Demuestre que a d − 1 es un divisor de a n − 1 . b Deduzca de la pregunta anterior que 2 2004 − 1 es divis-ible por 7 , por 63 y luego por 9 . 3 Sean m y n dos números naturales distintos de cero y d su pgcd . a Definimos m y n por m = d · m y n = d · n . Aplicando el teorema de Bézout a m y n , demuestre que existen números enteros relativos u y v tales que : m · u − n · v = d . b Supongamos que u y v son estrictamente positivos. Demostrar que : a m · u − 1 − a n · v − 1 · a d = a d − 1 A continuación, demostrar que a d − 1 es el pgcd de : a m · u − 1 et a n · v − 1 . c Calcular, utilizando el resultado anterior, el MCD de : 2 63 − 1 et 2 60 − 1 3. Teorema de Gauss E.3630 Sea ( E ) el conjunto de enteros naturales escritos, en base 10, de la forma abba donde a es un dígito mayor o igual que 2 y b es cualquier dígito. Ejemplos de elementos de ( E ) : 2002 ; 3773 ; 9119 . Número de ( E ) elementos que tienen 11 como factor más pequeño premier 1 a Descomponga 1001 en un producto de factores pri-mos. b Demuestra que cualquier elemento de ( E ) es divisible por 11 . 2 a ¾Cuál es el número de elementos de ( E ) ? b ¾Cuál es el número de elementos de ( E ) que no son https://chingmath.fr chapExoCorrec/3246 sacados/3246 chapExoCorrec/3226 sacados/3226 chapExoCorrec/3741 sacados/3741 France Juin 2004 5 points chapExoCorrec/3630 sacados/3630
divisibles ni por 2 ni por 5 ? 3 ser n un elemento de ( E ) escrito en la forma abba . a Demuestre que : ˇ n es divisible por 3 es equivalente a a + b es divisible por 3 ı b Demuestre que : ˇ n es divisible por 7 es igual a b es divisible por 7 ı 4 Deduce de las preguntas anteriores el número de elemen-tos de ( E ) que admiten 11 como menor factor primo. E.3837 Sea A el conjunto de los enteros naturales en el intervalo 1 ; 46] . 1 Consideramos la ecuación : ( E ) : 23 · x + 47 · y = 1 donde x et y sont enteros relativos. a Da una solución particular x 0 ; y 0 de ( E ) . b Determina el conjunto de ( x ; y ) soluciones de ( E ) . c Deduzca que existe un único número entero x perteneciente a A tal que : 23 · x ≡ 1 ( mod. 47) 2 Digamos a y b dos enteros relativos. a Muestra que si a · b ≡ 0 ( mod. 47) alors: a ≡ 0 ( mod. 47) ou b ≡ 0 ( mod. 47) . b Deducir que si a 2 ≡ 1 ( mod. 47) entonces : a ≡ 1 ( mod. 47) ; a ≡ − 1 ( mod. 47) 3 a Demostrar que para todo entero p de A , existe un entero relativo q tal que : p × q ≡ 1 ( mod. 47) . Para lo que sigue, se admite que para todo entero p de A , ex-iste un único entero, denotado inv ( p ) , perteneciente a A tal que : p × inv ( p ) ≡ 1 ( mod. 47) . Por ejemplo : inv (1) = 1 porque 1 × 1 ≡ 1 ( mod. 47) ; inv (2) = 24 porque 2 × 24 ≡ 1 ( mod. 47) ; inv (3) = 16 porque 3 × 16 ≡ 1 ( mod. 47) . b ¾Cuáles son los números enteros p de A que verifican : p = inv ( p ) c Demuestre que : 46! ≡ − 1 ( mod. 47) 4. Ecuación diofantina E.3198 Parte A : Pregunta del curso 1 Enuncia el teorema de Bézout y el teorema de Gauss. 2 Demuestra el teorema de Gauss utilizando el teorema de Bézout. Parte B Se trata de resolver en Z el sistema : ( S ) n ≡ 13 ( mod. 19) n ≡ 6 ( mod. 12) 1 Demuestre que existe un par ( u ; v ) de números enteros relativos tal que : 19 u + 12 v = 1 (En esta pregunta no se pide dar un ejemplo de tal par) Verificar que el entero N =13 × 12 v +6 × 19 u es una solu-ción de ( S ) para tal par. 2 a Sea n 0 una solución de ( S ) , verificar que el sistema ( S ) equivale a: n ≡ n 0 ( mod. 19) n ≡ n 0 ( mod. 12) b Demuestre que el sistema n ≡ n 0 ( mod. 19) n ≡ n 0 ( mod. 12) equivale a: n ≡ n 0 ( mod. 12 × 19) . 3 a Encontrar un par ( u ; v ) solución de la ecuación 19 u +12 v =1 y calcular el valor de N correspondiente. b Determinar el conjunto de soluciones de ( S ) (se puede utilizar la pregunta 2 b ) . 4 Un número natural n es tal que cuando se divide por 12 el resto es 6 y cuando se divide por 19 el resto es 13 . Dividimos n entre 228=12 × 19 . ¾Cuál es el resto r de esta división? E.3258 Recordemos que 2 003 es un entero primo. 1 a Determinar dos enteros relativos u y v tales que : 123 u + 2003 v = 1 b Deducir un entero relativo k 0 tal que : 123 k 0 ≡ 1 ( mod. 2003) c Demuestre que, para cualquier entero relativo x , 123 x ≡ 456 ( mod. 2003) si, y sólo si, x ≡ 456 k 0 ( mod. 2003) d Demuestre que existe un único número entero n tal que : 1 n 2002 et 123 n ≡ 456 ( mod. 2003) . 2 Sea a un número entero tal que : 1 a 2002 a Determine : pgcd ( a ; 2003) Deducir que existe un número entero m tal que : a · m ≡ 1 ( mod. 2003) b Demuestra que, para cualquier entero b , existe un único entero x tal que : 0 x 2 002 ; a · x ≡ b ( mod. 2003) https://chingmath.fr chapExoCorrec/3837 sacados/3837 chapExoCorrec/3198 sacados/3198 chapExoCorrec/3258 sacados/3258 France Septembre 2003 5 points
E.3256 Sea la ecuación (1) de incógnita racional x : 78 x 3 + u · x 2 + v · x − 14 = 0 donde u y v son enteros relativos. 1 Se supone en esta pregunta que 14 39 es solución de la ecuación (1) . a Demuestra que los enteros u y v están relacionados por la relación: 14 u + 39 v = 1129 b Utiliza el algoritmo de Euclides, detallando los distin-tos pasos del cálculo, para encontrar un par ( x ; y ) de enteros relativos que verifiquen la ecuación : 14 x + 39 y = 1 Verifica que el par ( − 25 ; 9) es una solución de esta ecuación. c Deducir un par ( u 0 ; v 0 ) solución particular de la ecuación : 14 u + 39 v = 1129 Dar la solución general de esta ecuación, es decir, el conjunto de pares ( u ; v ) de números enteros relativos que la verifican. d Determinar, entre los pares ( u ; v ) anteriores, aquella para la que el entero u es el entero natural más pe-queño posible. 2 a Descomponer 78 y 14 en factores primos. Deduzca, en N , el conjunto de divisores de 78 y el con-junto de divisores de 14. b Sea P Q una solución racional de la ecuación (1) de in-cógnita x : 78 x 3 + ux 2 + vx − 14 = 0 donde u y v son números enteros relativos. Demuestra que si P y Q son números enteros relativos primos entre sí, entonces P divide a 14 y Q divide a 78. c Deduzca el número de racionales, no enteros, que pueden ser soluciones de la ecuación (1) y escriba, en-tre estos racionales, el conjunto de aquellos que son positivos. E.3477 Las partes A y B son independi-entes. Parte A Consideremos la ecuación ( E ): 7 x − 6 y =1 donde x y y son números naturales. 1 Dar una solución particular de la ecuación ( E ) . 2 Determine el conjunto de pares de números naturales que son soluciones de la ecuación ( E ) . Parte B En esta parte, se propone determinar los pares ( n ; m ) de números naturales distintos de cero que satisfacen la relación: 7 n − 3 × 2 m = 1 ( F ) 1 Supongamos que m 4 . Demuestra que hay exactamente dos pares de soluciones. 2 Supongamos ahora que m 5 . a Demostrar que si el par ( n ; m ) verifica la relación ( F ) entonces : 7 n ≡ 1 ( mod. 32) b Al estudiar los restos de la división por 32 de las po-tencias de 7 , se demuestra que si el par ( n ; m ) verifica la relación ( F ) entonces n es divisible por 4. c Deduzca que si el par ( n ; m ) verifica la relación ( F ) entonces : 7 n ≡ 1 ( mod. 5) . d Para m 5 , ¾existen pares ( n ; m ) de números naturales que cumplan la relación ( F ) ? 3 Concluir, es decir, determinar el conjunto de pares de números naturales distintos de cero que satisfacen la relación ( F ) . https://chingmath.fr chapExoCorrec/3256 sacados/3256 Antilles-Guyane Septembre 2003 4 points chapExoCorrec/3477 sacados/3477
E.3905 Las preguntas 1 y 2 son inde-pendientes. Sea n un número natural distinto de cero. 1 Consideremos la ecuación ( E ) : 3 x + 7 y = 10 2 n donde x y y son números enteros relativos. a Determinar un par ( u ; v ) de números enteros relativos tales que : 3 · u + 7 · v = 1 Deduzca una solución particular ( x 0 ; y 0 ) de la ecuación ( E ) . b Determinar el conjunto de pares de números enteros relativos ( x ; y ) soluciones de ( E ) . 2 Consideremos la ecuación ( G ) : 3 x 2 + 7 y 2 = 10 2 n donde x y y son números enteros relativos. a Demuestre que : 100 ≡ 2 ( mod. 7) . Demostrar que si ( x ; y ) es solución de ( G ) entonces : 3 x 2 ≡ 2 n ( mod. 7) . b Reproduzca y complete la siguiente tabla : Resto de la división euclidiana de x por 7 0 1 2 3 4 5 6 Resto de la división euclidiana de 3 x 2 por 7 c Demostrar que 2 n es congruente con 1 , 2 o 4 módulo 7 . De ello se deduce que la ecuación ( G ) no tiene solución. E.5432 Parte A - Restitución organi-zada de conocimientos Requisitos previos: A continuación se recuerdan el teo-rema de Bézout y el teorema de Gauss. Teorema de Bézout: Dos números enteros relativos a y b son primos entre sí si, y solo si, existe un par ( u ; v ) de números enteros relativos que satisfacen a · u + b · v =1 . Teorema de Gauss: Sean a , b , c números enteros relativos. Si a divide el producto b · c y si a y b son primos entre sí, entonces a divide c 1 Utilizando el teorema de Bézout, demuestre el teorema de Gauss. 2 Sean p y q dos números naturales tales que p y q son primos entre sí. Deduzca del teorema de Gauss que, si a es un entero rel-ativo, tal que a ≡ 0 ( mod. p ) y a ≡ 0 ( mod. q ) , entonces a ≡ 0 ( mod. pq ) Parte B Se propone determinar el conjunto S de los enteros relativos n que verifican el sistema : n ≡ 9 ( mod. 17) n ≡ 3 ( mod. 5) 1 Búsqueda de un elemento de S . Se designa por ( u ; v ) un par de números enteros relativos tales que : 17 · u +5 · v =1 a Justificar la existencia de tal par ( u ; v ) . b Se establece : n 0 =3 × 17 u +9 × 5 v Demostrar que n 0 pertenece a S . c Dar un ejemplo de un entero n 0 que pertenezca a S . 2 Caracterización de los elementos de S . a Sea n un entero relativo que pertenece a S . Demostrar que : n − n 0 ≡ 0 ( mod. 85) . b Deduzca que un entero relativo n pertenece a S si, y solo si, puede escribirse en la forma n =43+85 k , donde k es un entero relativo. 3 Aplicación. Zoe sabe que tiene entre 300 y 400 fichas. Si hace montones de 17 fichas, le quedan 9 . Si hace montones de 5 fichas, le quedan 3 . ¾Cuántas fichas tiene? E.3322 1 a ¾Cuál es el resto de la división euclidiana de 6 10 en-tre 11 ? Justifica tu respuesta. b ¾Cuál es el resto de la división euclidiana de 6 4 entre 5? Justifica tu respuesta. c Deduzca las dos congruencias : 6 40 ≡ 1 ( mod. 11) ; 6 40 ≡ 1 ( mod. 5) . d Demuestra que 6 40 − 1 es divisible por 55 . 2 En esta pregunta, x y y designan números enteros rela-tivos. a Demuestra que la ecuación : ( E ): 65 · x − 40 · y =1 no tiene solución. b Demostrar que la ecuación : ( E ): 17 · x − 40 · y =1 admite al menos una solución. c Determinar, utilizando el algoritmo de Euclides, un par de números enteros relativos que sean soluciones de la ecuación ( E ) . d Resolver la ecuación ( E ) . Deducir que existe un único número natural x 0 menor que 40 tal que : 17 x 0 ≡ 1 ( mod. 40) 3 Para todo número natural a , demostrar que : Si a 17 ≡ b ( mod. 55) a 40 ≡ 1 ( mod. 55) entonces b 33 ≡ a ( mod. 55) 5. Problema de codificación E.5456 Parte A : Restitución organizada del conocimiento Sean a , b , c , d números enteros relativos y n un número nat- ural distinto de cero. Demuestre que si a ≡ b ( mod. n ) y si c ≡ d ( mod. n ) entonces ac ≡ bd ( mod. n ) . https://chingmath.fr chapExoCorrec/3905 sacados/3905 chapExoCorrec/5432 sacados/5432 chapExoCorrec/3322 sacados/3322 chapExoCorrec/5456 sacados/5456
Parte B: Inverso de 23 módulo 26 Consideremos la ecuación : ( E ): 23 x − 26 y =1 donde x y y denotan dos números enteros relativos. 1 Comprueba que el par ( − 9 ; − 8) es solución de la ecuación ( E ) . 2 Resolver entonces la ecuación ( E ) . 3 Deduzca un número entero a tal que : 0 a 25 ; 23 a ≡ 1 ( mod. 26) Parte C : Cifrado de Hill Queremos codificar una palabra de dos letras siguiendo el siguiente procedimiento : Paso 1 Cada letra de la palabra se sustituye por un número entero utilizando la tabla siguiente : 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 Se obtiene un par de números enteros ( x 1 ; x 2 ) donde x 1 corresponde a la primera letra de la palabra y x 2 corre-sponde a la segunda letra de la palabra. Paso 2 ( x 1 ; x 2 ) se transforma en ( y 1 ; y 2 ) tal que : ( S 1 ) : y 1 ≡ 11 x 1 + 3 x 2 ( mod. 26) y 2 ≡ 7 x 1 + 4 x 2 ( mod. 26) con 0 y 1 25 y 0 y 2 25 . Paso 3 ( y 1 ; y 2 ) se transforma en una palabra de dos le-tras utilizando la tabla de correspondencias dada en el paso 1 . Ejemplo : TE  palabra sin cifrar etapa 1 anchura0pt profundidad5pt = ⇒ (19 ; 4) etapa 2 anchura0pt profundidad5pt = ⇒ (13 ; 19) etapa 3 anchura0pt profundidad5pt = ⇒ NT  palabra clave 1 Codificar la palabra ST . 2 Ahora queremos determinar el procedimiento de descod-ificación: a Demuestre que cualquier par ( x 1 ; x 2 ) que verifica las ecuaciones del sistema ( S 1 ) , cumple las ecuaciones del sistema : ( S 2 ) : 23 x 1 ≡ 4 y 1 + 23 y 2 ( mod. 26) 23 x 2 ≡ 19 y 1 + 11 y 2 ( mod. 26) b Utilizando la parte B , demuestre que cualquier par ( x 1 ; x 2 ) que verifica las ecuaciones del sistema ( S 2 ) , cumple las ecuaciones del sistema : ( S 3 ) : x 1 ≡ 16 y 1 + y 2 ( mod. 26) x 2 ≡ 11 y 1 + 5 y 2 ( mod. 26) c Demuestra que cualquier par ( x 1 ; x 2 ) que cumple las ecuaciones del sistema ( S 3 ) , cumple las ecuaciones del sistema ( S 1 ) . d Decodificar la palabra Y J E.3324 Parte A Consideremos la ecuación ( E ): 11 x − 26 y =1 , donde x y y des-ignan dos números enteros relativos. 1 Verifique que el par ( − 7 ; − 3) es solución de ( E ) . 2 Resuelva entonces la ecuación ( E ) . 3 Deduzca el par de números enteros relativos ( u ; v ) solu-ción de ( E ) tal que : 0 u 25 . Parte B Asimilamos cada letra del alfabeto a un número entero, tal y como se indica en la tabla siguiente : 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 Se ˇ codifica ı cualquier número entero x comprendido entre 0 y 25 de la siguiente manera : Se calcula 11 x +8 . Se calcula el resto de la división euclidiana de 11 x +8 por 26, que se denomina y . x se codifica entonces como ˇ codificado ı por y . Así, por ejemplo, la letra L se asimila al entero 11 ; 11 × 11+8= 129 o 129 ≡ 25 ( mod. 26) ; 25 es el resto de la división euclid-iana de 129 por 26. Al número entero 25 le corresponde la letra Z . Por lo tanto, la letra L se codifica con la letra Z . 1 Codificar la letra W . 2 El objetivo de esta pregunta es determinar la función de descodificación. a Demostrar que para todos los números enteros rela-tivos x y j , se tiene : 11 · x ≡ j ( mod. 26) equivale a x ≡ 19 · j ( mod. 26) . b Deduzca un proceso de descodificación. c Descodifique la letra W . 6. Aritmética y geometría E.3264 1 a Sea p un número natural. Demuestre que uno de los tres números naturales p , p +10 y p +20 , y solo uno, es divisible por 3. b Los números naturales a , b y c son, en este orden, los tres primeros términos de una sucesión aritmética de razón 10. Determina estos tres números enteros sabi-endo que son primos. 2 Sea E el conjunto de tripletas de números enteros rela-tivos ( u ; v ; w ) tales que : 3 · u + 13 · v + 23 · w = 0 a Demuestre que para una tripleta de este tipo: v ≡ https://chingmath.fr chapExoCorrec/3324 sacados/3324 Antilles-Guyane Juin 2008 5 points chapExoCorrec/3264 sacados/3264
-123456789I-123456789JO w ( mod. 3) b Se establece v =3 k + r y w =3 k + r donde k , k y r son números enteros relativos y 0 r 2 . Demuestre que los elementos de E son de la forma : − 13 k − 23 k − 12 r ; 3 k + r ; 3 k + r c El espacio se refiere a un sistema de coordenadas ortonormales con origen O y sea P el plano de ecuación 3 x +13 y +23 z =0 . Determinar el conjunto de puntos M con coordenadas ( x ; y ; z ) enteras relativas que pertenecen al plano P y están situados dentro del cubo de centro O , de lado 5 y cuyas aristas son paralelas a los ejes. E.3325 Sean a y b dos números naturales distintos de cero; el conjunto de puntos del plano se denomina ˇ réseau ı asociado a los enteros a y b , provisto de un sistema de coordenadas ortonormal, cuyas coordenadas ( x ; y ) son números enteros que satisfacen las condiciones : 0 x a ; 0 y b Este grafo se denota por R a,b . El objetivo del ejercicio es relacionar ciertas propiedades ar-itméticas de los números enteros x y y con propiedades ge-ométricas de los puntos correspondientes del grafo. A - Representación gráfica de algunos conjuntos En esta pregunta se esperan respuestas sin explicación, en forma de gráfico que se cumplimentará debidamente en la hoja adjunta que se devolverá con la copia. Represente gráficamente los puntos M ( x ; y ) de la red R 8 , 8 verificando : 1 x ≡ 2 ( mod. 3) y y ≡ 1 ( mod. 3) , en el gráfico 1 de la hoja adjunta. 2 x + y ≡ 1 ( mod. 3) , en el gráfico 2 de la hoja anexa. 3 x ≡ y ( mod. 3) , en el gráfico 3 de la hoja anexa. B - Resolución de una ecuación Considera la ecuación ( E ): 7 x − 4 y =1 , donde las incógnitas x y y son enteros relativos. 1 Determina un par de enteros relativos ( x 0 ; y 0 ) solución de la ecuación ( E ) . 2 Determinar el conjunto de pares de números enteros rel-ativos que son soluciones de la ecuación ( E ) . 3 Demostrar que la ecuación ( E ) admite una única solu-ción ( x ; y ) para la cual el punto M ( x ; y ) correspondiente pertenece a la red R 4 , 7 . C - Una propiedad de los puntos situados en la diag-onal de la red. Si a y b son dos números naturales distintos de cero, consid-eramos la diagonal [ OA ] de la red R a,b con O (0 ; 0) y A ( a ; b ) . 1 Demuestra que los puntos del segmento [ OA ] se caracter-izan por las condiciones : 0 x a ; 0 y b ; a · y = b · x 2 Demuestre que si a y b son primos entre sí, entonces los puntos O y A son los únicos puntos del segmento [ OA ] que pertenecen a la red R a,b . 3 Demostrar que si a y b no son primos entre sí, entonces el segmento [ OA ] contiene al menos otro punto de la red. (Se puede considerar el MCD d de los números enteros a y b y establecer a = d · a y b = d · b ) Gráfico 1 Gráfico 2 Gráfico 3 https://chingmath.fr chapExoCorrec/3325 sacados/3325 Asie Juin 2008 5 points -123456789I-123456789JO -123456789I-123456789JO -123456789I-123456789JO
7. Aritmética y secuencias E.3254 Considere la secuencia u n de números naturales definida por: u 0 = 14 u n +1 = 5 u n − 6 para cualquier número natural n 1 Calcule u 1 , u 2 , u 3 y u 4 . ¾Qué conjetura puede hacerse sobre las dos últimas cifras de u n ? 2 Demuestre que, para cualquier número natural n : u n +2 ≡ u n ( mod. 4) . Deduzca que, para cualquier número natural k : u 2 k ≡ 2 ( mod. 4) et u 2 k +1 ≡ 0 ( mod. 4) . 3 a Demuestre por recurrencia que, para cualquier n ∈ N : 2 u n = 5 n +2 + 3 . b Deduzca que, para cualquier número natural n : 2 u n ≡ 28 ( mod. 100) . 4 Determine las dos últimas cifras de la forma decimal de u n según los valores de n . 5 Demuestre que la PGCD de dos términos consecutivos de la sucesión ( u n ) es constante. Especifique su valor. E.3574 1 Calcular el PGCD de 4 5 − 1 y de 4 6 − 1 . Sea u la sucesión numérica definida por: u 0 = 0 u 1 = 1 u n +2 = 5 · u n +1 − 4 · u n para todo número natural n 2 Calcular los términos u 2 , u 3 y u 4 de la sucesión u . 3 a Demuestre que la sucesión u verifica, para todo número natural n : u n +1 = 4 · u n + 1 b Demuestre que, para todo número natural n , u n es un número natural. c Deduzca, para todo número natural n , el PGCD de u n y u n +1 . 4 Sea v la sucesión definida para todo número natural n por: v n = u n + 1 3 a Demostrar que v es una sucesión geométrica cuya razón y primer término v 0 se determinarán. b Expresar v n y luego u n en función de n . c Determinar, para todo número natural n , el PGCD de 4 n +1 − 1 y de 4 n − 1 . E.6252 Consideramos la función f de un algoritmo que toma como argumentos dos números naturales A et B comprobando A < B : Función f(A,B) D ← B − A Tant que D>0 B ← de A A ← de D Si B>A Alors D ← de B − A Sinon D ← de A − B Fin Si Fin Tant que Renvoyer A 1 On llama a la función f con como valores argumentales : A =12 y B =14 . La tabla siguiente se completará indicando los valores sucesivos que toman las variables A , B et D durante la llamada a esta función. A B D 12 14 2 L la llamada a la función f calcula el valor de la PGCD de los enteros A et B . Al introducir A =221 y B =331 , la llamada a la función f devuelve el valor 1 . a justificar que existen pares ( x ; y ) de enteros relativos solución de la ecuación : ( E ) : 221 · x − 331 · y = 1 b Vérifier que el par (3 ; 2) es solución de la ecuación ( E ) . Deducir el conjunto de pares ( x ; y ) de enteros relativos que son solución de la ecuación ( E ) . 3 On Considerar las sucesiones de números naturales u n y v n definidas para cualquier número natural n por: u n = 2 + 221 · n ; v 0 = 3 v n +1 = v n + 331 a Exprimer v n como función del número natural n . b Determinar todos los pares de números naturales ( p ; q ) tales que : u p = v q ; 0 p 500 ; 0 q 500 https://chingmath.fr chapExoCorrec/3254 sacados/3254 chapExoCorrec/3574 sacados/3574 chapExoCorrec/6252 sacados/6252
ABCDEFGH 8. Ejercicios no clasificados E.1604 Para cada una de las cinco proposi-ciones siguientes, indique si es verdadera o falsa y justifique su respuesta. Las respuestas sin justificar no obtendrán ningún punto. Proposición 1: Para todo número natural n , 3 divide al número entero 2 2 n − 1 Proposición 2: Si un número entero relativo x es solución de la ecuación x 2 + x ≡ 0 ( mod. 6) , entonces x ≡ 0 ( mod. 3) Proposición 3: El conjunto de pares de números en-teros relativos ( x ; y ) que son soluciones de la ecuación 12 · x − 5 · y =3 es el conjunto de pares (4+10 · k ; 9+24 · k ) donde k ∈ Z Proposición 4: Existe un único par ( a ; b ) de números en-teros naturales, tal que : a<b y PPCM ( a ; b ) − PGCD ( a ; b )=1 . Dos números naturales M y N son tales que M se escribe abc en base diez y N se escribe bca en base diez. Proposición 5: Si el número entero M es divisible por 27 , entonces el número entero M − N también es divisible por 27 . E.3133 1 Consideremos la ecuación : ( E ) : 17 x − 24 y = 9 donde ( x ; y ) es un par de números enteros relativos. a Comprueba que el par (9 ; 6) es solución de la ecuación ( E ) . b Resolver la ecuación ( E ) . 2 En una feria, Jean se sube a una atracción circular rep-resentada en el esquema del anexo 2. Puede sentarse en cualquiera de los ocho puntos indicados en el círculo. La atracción incluye un juego que consiste en atrapar un pompón que se desplaza por un cable que forma un cuadrado en el que se inscribe el círculo. La atracción gira en el sentido de las agujas del reloj, a velocidad con-stante. Da una vuelta a velocidad constante. Da una vuelta en 24 segundos. El pompón se mueve en la misma dirección a velocidad constante. Da una vuelta en 17 se-gundos. Para ganar, Jean debe atrapar el pompón, y solo puede hacerlo en los puntos de contacto que se indican con A , B , C y D en el dibujo. En el instante t =0 , Jean parte del punto H al mismo tiempo que el pompón parte del punto A . a Supongamos que en un momento dado t Jean atrapa el pompón en A . Jean ya ha podido pasar varias veces por A sin encontrar el pompón. En el instante t , anota-mos y el número de vueltas realizadas desde su primera pasada en A y x el número de vueltas realizadas por el pompón. Demostrar que ( x ; y ) es la solución de la ecuación ( E ) de la pregunta 1. b Jean ha pagado por 2 minutos ; ¾tendrá tiempo de atra-par el pompón? c Demuestra que, en realidad, solo es posible atrapar el pompón en el punto A . d Jean sale ahora del punto E . ¾Tendrá tiempo de atra-par el pompón en A antes de que pasen los dos minu-tos? https://chingmath.fr chapExoCorrec/1604 sacados/1604 Polynesie Juin 2006 5 pionts chapExoCorrec/3133 sacados/3133 ABCDEFGH
E.6249 Parte A El objetivo de esta parte es demostrar que el conjunto de los números primos es infinito mediante un razonamiento por contradicción. 1 Supongamos que existe un número finito de números pri-mos denotados por p 1 , p 2 , . . . , p n . Consideramos el entero E producto de todos los números primos aumentados en 1 : E = p 1 × p 2 × · · · × p n + 1 Demuestre que E es un número entero mayor o igual que 2 , y que E es primo con cada uno de los números enteros p 1 , p 2 , . . . , p n . 2 Utilizando el hecho de que E admite un divisor primo, concluya. Parte B Para todo número natural k 2 , se establece : M k =2 k − 1 . Se dice que M k es el número k de Mersenne. 1 a Reproduce y completa la siguiente tabla, que da al-gunos valores de M k : k 2 3 4 5 6 7 8 9 10 M k b Según la tabla anterior, si k es un número primo, ¾se puede conjeturar que el número M k es primo? 2 Sean p y q dos números naturales distintos de cero. a Justificar la igualdad : 1 + 2 p + 2 p 2 + · · · + 2 p q − 1 = 2 p q − 1 2 p − 1 b Deducir que 2 p · q − 1 es divisible por 2 p − 1 . c Deduzca que si un número entero k mayor o igual a 2 no es primo, entonces M k tampoco lo es 3 a Demuestre que el número de Mersenne M 11 no es primo. b ¾Qué se puede deducir sobre la conjetura de la pre-gunta? 1 b ? Parte C La prueba de Lucas-Lehmer permite determinar si un número de Mersenne dado es primo. Esta prueba utiliza la sucesión numérica u n definida por u 0 =4 y para todo número natural n : u n +1 = u n 2 − 2 Si n es un número natural mayor o igual que 2 , la prueba permite afirmar que el número entero M n es primo si, y solo si, u n − 2 ≡ 0 ( mod. M n ) . Esta propiedad se admite en la sucesión. 1 Utilizar la prueba de Lucas-Lehmer para comprobar que el número de Mersenne M 5 es primo. 2 La función del siguiente algoritmo toma como argumento un entero n mayor o igual que 3 y debe devolver 1 si el número de Mersenne M n es primo y 0 en caso contrario, utilizando la prueba de Lucas-Lehmer Función f(n) u ← 4 M ← ... Para i que va de 1 a ... u ← ... Fin Para Si M divide u Entonces Devolver ...... Si no Devolver ...... Fin Si Copie y complete el código de la función f para que cumpla la condición deseada. E.3552 Parte I Sea x un número real. 1 Demuestra que : x 4 +4= x 2 +2 2 − 4 · x 2 . 2 Deduce que x 4 +4 puede escribirse como el producto de dos trinomios con coeficientes enteros. Parte II Sea n un número natural mayor o igual que 2 . Considera los enteros : A = n 2 − 2 n +2 ; B = n 2 +2 n +2 y d su PGCD . 1 Demuestra que n 4 +4 no es primo. 2 Demuestra que, cualquier divisor de A que divide a n , divide a 2 . 3 Demuestra que, cualquier divisor común de A y B , divide a 4 n . 4 En esta pregunta, se supone que n es impar. a Demuestra que A y B son impares. Deduce que d es impar. b Demuestra que d divide a n . c Deduce que d divide a 2 , luego, que A y B son primos entre sí. 5 Se supone ahora que n es par. a Demuestra que 4 no divide a n 2 − 2 n +2 . b Demuestre que d es de la forma d =2 · p , donde p es impar. c Demuestra que p divide a n . Deduce que d =2 . (Puede basarse en la demostración utilizada en la pregunta 4 ) . https://chingmath.fr chapExoCorrec/6249 sacados/6249 Asie Juin 2014 chapExoCorrec/3552 sacados/3552
E.6928 Para todo número natural n dis-tinto de cero, llamamos S ( n ) al número igual a la suma de los divisores positivos de n . 1 Verifique que S (6)=12 y calcule S (7) . 2 a Demuestra que, para todo número natural n mayor o igual que 2 : S ( n ) 1+ n b ¾Cuáles son los números naturales n tales que S ( n )= 1+ n ? 3 En esta pregunta se supone que n se escribe p × q où p y q son números primos distintos. a Demuestra que : S ( n )= 1+ p 1+ q . b Consideremos la siguiente proposición : ˇ Para todos los números naturales n y m distintos de cero, S n × m = S n × S m ı ¾Es verdadera o falsa esta proposición? Justificar. 4 En esta pregunta se supone que el entero n se escribe p k , donde p es un entero primo y k un entero natural distinto de cero. a ¾Cuáles son los divisores de n ? b Deduzca que : S ( n )= 1 − p k +1 1 − p . 5 En esta pregunta se supone que n se escribe p 13 × q 7 , donde p y q son números enteros primos distintos. a Sea m un número natural. Demuestre que m divide a n si, y solo si, existen dos números enteros s y t con 0 s 13 y 0 t 7 tales que m = p s × q t . b Demostrar que : S ( n )= 1 − p 14 1 − p × 1 − q 8 1 − q E.6946 Para cualquier par de números enteros relativos distintos de cero ( a ; b ) , se denota por pgcd ( a ; b ) el máximo común divisor de a y b . El plano está provisto de un sistema de coordenadas O ; −→ i ; −→ j . 1 Ejemplo. Sea Δ 1 la recta de ecuación : y = 5 4 · x − 2 3 a Demuestra que si ( x ; y ) es un par de enteros relativos, entonces el entero 15 · x − 12 · y es divisible por 3 . b ¾Existe al menos un punto de la recta Δ 1 cuyas coorde-nadas sean dos números enteros relativos? Justificar. Generalización : Consideremos ahora una recta Δ cuya ecuación es : y = m n · x − p q donde m , n , p y q son números enteros relativos distintos de cero, tales que : pgcd ( m ; n ) = pgcd ( p ; q ) =1 Así, los coeficientes de la ecuación ( E ) son fracciones irre-ducibles y se dice que Δ es una recta racional. El objetivo del ejercicio es determinar una condición necesaria y suficiente sobre m , n , p y q para que una recta racional Δ tenga al menos un punto cuyas coordenadas sean dos números enteros relativos. 2 Supongamos aquí que la recta Δ tiene un punto de co-ordenadas x 0 ; y 0 , donde x 0 y y 0 son números enteros relativos. a Observando que el entero n · y 0 − m · x 0 es un entero rel-ativo, demuestre que q divide el producto n · p b Deduzca que q divide n . 3 Recíprocamente, supongamos que q divide a n y quere-mos encontrar un par x 0 ; y 0 de números enteros rela-tivos tales que : y 0 = m n · x 0 − p q . a Se establece n = q · r , donde r es un entero relativo dis-tinto de cero. Demostrar que se pueden encontrar dos enteros relativos u y v tales que : q · r · u − m · v =1 . b Deduzca que existe un par ( x 0 ; y 0 ) de enteros relativos tales que : y 0 = m n · x 0 − p q 4 Sea Δ la recta de ecuación y = 3 8 · x − 7 4 . ¾Tiene esta recta un punto cuyas coordenadas son números enteros rela-tivos? Justificar. 5 Consideremos la función f de un algoritmo que toma como argumento los números enteros M , N , P et Q . Además, supongamos que los argumentos pasados durante la lla-mada a la función f verifican : pgcd ( M ; N )= pgcd ( P ; Q )=1 Función f(M,N,P,Q) Si Q divide N Entonces X ← 0 Mientras M N · X − P Q no sea entero y − M N · X − P Q no sea entero X ← X+1 Fin Mientras que https://chingmath.fr chapExoCorrec/6928 sacados/6928 chapExoCorrec/6946 sacados/6946
Si M N X − P Q es entero Entonces Devolver X ; M N · X − P Q Si no Devolver − X ; M N · X − P Q Fin Si Si no Devolver "Sinsolución" Fin si a Justificar que la llamada a la función f finaliza para todos los valores pasados como argumento de M , N , P , Q , enteros relativos distintos de cero que verifican : pgcd ( M ; N ) = pgcd ( P ; Q ) = 1 b ¾Qué permite obtener? E.3551 Sea p un número primo dado. Se propone estudiar la existencia de pares ( x ; y ) de números nat-urales estrictamente positivos que satisfagan la ecuación : ( E ) : x 2 + y 2 = p 2 1 Se establece p =2 . Demostrar que la ecuación ( E ) no tiene solución. Supongamos ahora p =2 y que el par ( x ; y ) es solución de la ecuación ( E ) . 2 El objetivo de esta pregunta es demostrar que x y y son primos entre sí. a Demostrar que x y y son de paridades diferentes. b Demostrar que x y y no son divisibles por p . c Deduzca que x y y son primos entre sí. 3 Supongamos ahora que p es una suma de dos cuadrados distintos de cero, es decir : p = u 2 + v 2 donde u y v son dos números naturales estrictamente positivos. a Comprueba que entonces el par ( | u 2 − v 2 | ; 2 · u · v ) es solución de la ecuación ( E ) . b Dar una solución de la ecuación ( E ) cuando p =5 y cuando p =13 . 4 Por último, proponemos verificar con dos ejemplos que la ecuación ( E ) es imposible cuando p no es la suma de dos cuadrados. a p =3 y p =7 ¾son la suma de dos cuadrados? b Demuestre que las ecuaciones x 2 + y 2 =9 y x 2 + y 2 =49 no admiten solución en números naturales estricta-mente positivos. E.5862 Se denota E el conjunto de los veintisiete números enteros comprendidos entre 0 y 26 . Denotamos por A el conjunto cuyos elementos son las vein-tiséis letras del alfabeto y un separador entre dos palabras, denotado por ˇ ? ı, considerado como un carácter. Para codificar los elementos de A , se procede de la siguiente manera : En primer lugar : se asocia a cada una de las letras del alfabeto, ordenadas alfabéticamente, un número entero natural comprendido entre 0 y 25 , ordenados de menor a mayor. Por lo tanto, tenemos : a ↦−→ 0 ; b ↦−→ 1 ; . . . ; z ↦−→ 25 . Asociamos al separador ˇ ? ı el número entero 26 . a b c d e f g h i j k l m n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 o p q r s t u v w x y z ? 14 15 16 17 18 19 20 21 22 23 24 25 26 Decimos que a tiene el rango 0 , b tiene rango 1 ,. . . , z tiene rango 25 y el separador ˇ ? ı tiene rango 26 . En segundo lugar: a cada elemento x de E , la aplicación g asocia el resto de la división euclidiana de 4 x +3 por 27 . Cabe señalar que, para todo x de E , g ( x ) pertenece a E . En tercer lugar: el carácter inicial se sustituye entonces por el carácter de rango g ( x ) . Ejemplo : s ↦−→ 18 ; g (18) = 21 ; 21 ↦−→ v . Por lo tanto, la letra s se sustituye durante la codificación por la letra v . 1 Encuentre todos los números enteros x de E tales que g ( x )= x , es decir, invariantes por la aplicación g . Deduzca todos los caracteres invariantes en esta codifi-cación. 2 Demuestre que, para todo número natural x perteneciente a E y todo número natural y perteneciente a E : Si y ≡ 4 x +3 ( mod. 27) entonces x ≡ 7 y +6 ( mod. 27) Deduzca que dos caracteres distintos están codificados por dos caracteres distintos. 3 Proponga un método de decodificación. 4 Decodifique la palabra ˇ vfv ı. https://chingmath.fr chapExoCorrec/3551 sacados/3551 chapExoCorrec/5862 sacados/5862
E.6903 Los números naturales 1 , 11 , 111 , 1111 . . . son rep-units. Así se denominan los números natu-rales que solo se escriben con 1 . Para todo número natural p distinto de cero, se denota por N p la unidad repetida que se escribe con p veces el número 1 : N p = 11 : : : 1  p répétitions du chiffre 1 = k = p − 1 k =0 10 k En todo el ejercicio, p designa un número natural distinto de cero. El objetivo de este ejercicio es estudiar algunas propiedades de las unidades repetidas. Parte A : divisibilidad de las unidades repetidas en algunos casos particulares 1 Demuestre que N p no es divisible ni por 2 ni por 5 . 2 En esta pregunta, se estudia la divisibilidad de N p por 3 . a Demuestre que, para todo número natural j : 10 j ≡ 1 ( mod. 3) b Deduzca que N p ≡ p ( mod. 3) . c Determinar una condición necesaria y suficiente para que el rep-unit N p sea divisible por 3 . 3 En esta pregunta, se estudia la divisibilidad de N p por 7 . a Copiar y completar la tabla de congruencias siguiente, donde a es el único entero relativo que pertenece a: − 3 ; − 2 ; − 1 ; 0 ; 1 ; 2 ; 3 tal que : 10 m ≡ a ( mod. 7) On no requiere justification . m 0 1 2 3 4 5 6 a b Soit p un número no natural nul Demuestre que 10 p ≡ 1 ( mod. 7) si, y sólo si, p es múlti-plo de 6 . Podemos utilizar la división euclídea de p por 6 . c Justificar que, para cualquier número natural distinto de cero p : N p = 10 p − 1 9 d Démontrer que ˇ 7 divide N p ı est equivalente a ˇ 7 di-vide 9 · N p ı. e En deduzca que N p es divisible por 7 si, y sólo si, p es múltiplo de 6 . Parte B: una rep-unidad estrictamente mayor que 1 nunca es un cuadrado perfecto 1 So n un número natural mayor o igual que 2 . Suponga que la escritura decimal de n 2 termina en el número 1 , es decir, n 2 ≡ 1 ( mod. 10) a Recopier y complete la siguiente tabla de congruen-cias : n ≡ : : : [10] 0 1 2 3 4 5 6 7 8 9 n 2 ≡ : : : [10] b En deduzca que existe un número natural m tal que : n = 10 · m + 1 ou n = 10 · m − 1 . c Concluya que : n 2 ≡ 1 ( mod. 20) . 2 Sea p un número natural mayor o igual que 2 . ¾Cuál es el resto de la división euclidiana de N p entre 20 ? 3 Deduzca que, para p número natural mayor o igual a 2 , el rep-unit N p no es el cuadrado de un número entero E.8134 A cada letra del alfabeto se le asigna un número entero x comprendido entre 0 y 25 , tal y como se indica en la tabla siguiente : Letra A B C D E F G H I J K L M x 0 1 2 3 4 5 6 7 8 9 10 11 12 Letra N O P Q R S T U V W X Y Z x 13 14 15 16 17 18 19 20 21 22 23 24 25 El ˇ número de RABIN ı es un dispositivo de cifrado asimétrico inventado en 1979 por el informático Michael Rabin. Alice quiere comunicarse de forma segura utilizando este sis-tema criptográfico. Elige dos números distintos p y q . Este par de números es su clave privada, que mantiene en secreto. A continuación, calcula n = p × q y elige un número natural B tal que 0 B n − 1 . Si Bob quiere enviar un mensaje secreto a Alice, lo codifica letra por letra. La codificación de una letra representada por el número en-tero x es el número y tal que : y ≡ x x + B ( mod. n ) con 0 y n En todo el ejercicio, tomamos p =3 , q =11 , por lo tanto n = p × q =33 y B =13 . Parte A : Cifrado Bob quiere enviar la palabra ˇ NO ı a Alice. 1 Demuestra que Bob codifica la letra ˇ N ı ı con el número 8 . 2 Determina el número que codifica la letra ˇ O ı. Parte B: Descifrado Alice ha recibido un mensaje cifrado que comienza con el número 3 Para descifrar este primer número, debe determinar el número entero x tal que : x x +3 ≡ 3 ( mod. 33) 0 x< 26 1 Demuestra que x · x +13 ≡ 3 ( mod. 33) equivale a: x + 23 2 ≡ 4 ( mod. 33) . 2 a Demuestra que si x +23 2 ≡ 4 ( mod. 33) , entonces el sistema de ecuaciones x + 23 2 ≡ 4 ( mod. 3) x + 23 2 ≡ 4 ( mod. 11) es válido. b Recíprocamente, demostrar que si x + 23 2 ≡ 4 ( mod. 3) x + 23 2 ≡ 4 ( mod. 11) entonces x +23 2 ≡ 4 ( mod. 33) c Deduzca que : x · x +13 ≡ 3 ( mod. 33) ⇐⇒ x +23 2 ≡ 1 ( mod. 3) x +23 2 ≡ 4 ( mod. 11) 3 a Determinar los números naturales a tales que 0 a< 3 y a 2 ≡ 1 ( mod. 3) . b Determinar los números naturales b tales que 0 b< 11 https://chingmath.fr chapExoCorrec/6903 sacados/6903 sacados/8134
y b 2 ≡ 4 ( mod. 11) . 4 a Deduzca que x · x +13 ≡ 3 ( mod. 33) equivale a los cuatro sistemas siguientes : x ≡ 2 ( mod. 3) x ≡ 8 ( mod. 11) ou x ≡ 0 ( mod. 3) x ≡ 1 ( mod. 11) ou x ≡ 2 ( mod. 3) x ≡ 1 ( mod. 11) ou x ≡ 0 ( mod. 3) x ≡ 8 ( mod. 11) b Se admite que cada uno de estos sistemas admite una única solución entera x tal que 0 x< 33 . Determine, sin justificación, cada una de estas solu-ciones. 5 Complete el algoritmo siguiente para que muestre las cu-atro soluciones encontradas en la pregunta anterior. Para...que va desde...à... Si el resto de la división de...par...es igual a...entonces Mostrar ... Fin Si Fin Para 6 ¾Puede Alice conocer la primera letra del mensaje envi-ado por Bob? ¾Se puede utilizar el ˇ número de RABIN ı ı para descod-ificar un mensaje letra por letra? E.8140 El objetivo de este ejercicio es ex-aminar un método de cifrado de clave pública de información digital, denominado sistema RSA, en honor a los matemáti-cos Ronald Rivest, Adi Shamir y Leonard Adleman, quienes inventaron este método de cifrado en 1977 y lo publicaron en 1978 . Las preguntas 1 et 2 son preguntas preparatorias, la pre-gunta 3 aborda el cifrado, la pregunta 4 el descifrado. 1 Esta pregunta plantea calcular el resto en la división eu-clidiana por 55 de ciertas potencias del entero 8 . a Verificar que 8 7 ≡ 2 ( mod. 55) . Deduzca el resto en la división euclidiana por 55 del número 8 21 . b Compruebe que 8 2 ≡ 9 ( mod. 55) , y luego deduzca de la pregunta a el resto en la división euclidiana por 55 de 8 23 . 2 En esta pregunta, consideramos la ecuación : ( E ) 23 · x − 40 · y =1 , cuyas soluciones son pares ( x ; y ) de números enteros rel-ativos. a Justifique el hecho de que la ecuación ( E ) admite al menos un par de soluciones. b Dé un par, solución particular de la ecuación ( E ) . c Determine todos los pares de números enteros relativos que son solución de la ecuación ( E ) . d Deduzca que existe un único entero d que cumple las condiciones : 0 d< 40 et 23 · d ≡ 1 ( mod. 40) . 3 Cifrado en el sistema RSA Una persona A elige dos números enteros primos p y q , y luego calcula los productos N = p · q y n = p − 1 q − 1 . También elige un número entero natural c primo con n . La persona A publica el par ( N ; c ) , que es una clave pública que permite a cualquiera enviarle un número cifrado. Los mensajes se digitalizan y se transforman en una se-cuencia de números enteros comprendidos entre 0 y n − 1 . Para cifrar un número entero a de esta secuencia, se pro-cede de la siguiente manera : se calcula el resto b en la división euclidiana por N del número a c , y el número cifrado es el número entero b . En la práctica, este método es seguro si la persona A elige números enteros primos p y q muy grandes, que se escriben con varias decenas de dígitos. Aquí lo veremos con números más sencillos : p =5 et q =11 . La persona A también elige c =23 . a Calcular los números N y n , y luego justificar que el valor de c cumple la condición deseada b Un emisor desea enviar a la persona A el número a =8 . Determinar el valor del número cifrado b . 4 Descifrado en el sistema RSA La persona A calcula en primer lugar el único número natural d que cumple las condiciones : 0 d<n et c · d ≡ 1 ( mod. n ) . Mantiene en secreto este número d , que le permite, y solo a ella, descifrar los números que le han sido envia-dos cifrados con su clave pública. Para descifrar un número cifrado b , la persona A calcula el resto a en la división euclidiana por N del número b d , y el número en claro, es decir, el número antes del cifrado, es el número a . Se admite la existencia y la unicidad del entero d , y el hecho de que el descifrado funciona. Los números elegidos por A siguen siendo p =5 , q =11 y c =23 . a ¾Cuál es el valor de d ? b Aplicando la regla de descifrado, encuentre el número en claro cuando el número cifrado es b =17 . E.8149 Sudamérica 2018 https://chingmath.fr sacados/8140 sacados/8149