Numeri in base n divisibilit e fattorizzazione

Page 1

Lemma 1. Siano a, b, c, d∈ Z, k, n∈ N∗, n ̸= 1. Si ha: (1) ( a≡ b (mod n)∧ c≡ d (mod n))⇒ a + c ≡ b + d (mod n) (2) ( a≡ b (mod n)∧ c≡ d (mod n))⇒ ac ≡ b (mod n) (3) a≡ b (mod n)⇒ ak≡ bk (mod n) Dimostrazione. Da a≡ b (mod n) e c≡ d (mod n) segue n| (a− b) e n| (c− d). Allora n| a− b + c− d, ovvero a| (a + c)− (b + d) e ci` o vuol dire chea + c ≡ b + d (mod n), per cui (1) ` e provata. Poich` ea≡ b (mod n) e c≡ d (mod n), allora n| (a− b) e n| (c− d) e quindi n| (a− b)c e n| (c− d)b. Pertanto n| (a− b)c + (c− d)b, cio´ en| ac− bd, ovvero ac ≡ bd (mod n), e (2) risulta verificata. Per provare (3) si procede per induzione completa su k. Per k = 1, certamente a1 ≡ b1 (mod n) ` e verificato poich´ ea1 = a, b 1 = b. Sia k∈ N, k > 1. Si suppone che sia ak≡ bk (mod n) e si deve provare che ak+1≡ bk+1 (mod n). Per ipotesi di induzione si ha ak≡ bk (mod n); inoltre, per ipotesi, a≡ b (mod n). Allora, usando (2), aka≡ bkb (mod n) e, ricordando che per ogni numero intero x, risulta xk+1 = xk· x, si ha ak+1≡ bk+1 (mod n). Teorema 1. Sia n∈ N∗, n̸= 1. Allora ∀a∈ N,∃|r0, . . . , rh∈ N tali che (1) a = rhnh + rh−1nh−1 +··· + r1n + r0. Dimostrazione. (cenno) Si eseguono le seguenti divisioni: a = q0 n + r0, r 0 < n q0 = q1 n + r1, r 1 < n q1 = q2 n + r2. r 2 < n ... qh−2 = qh−1 n + rh−1 rh−1 < n qh−1 = 0 n + rh rh < n Poich` e si tratta di numeri naturali, si ha q0 > q 1 > . . . , per cui, ad un certo punto il quoziente di una divisione si deve azzerare. Si ha, quindi: a = q0n + r0 = (q1n + r1)n + r0 = q1n2 + r1n + r0 = (q2n + r2)n2 + r1n + r0 = q2n3 + r2n2 + r1n + r0 =··· = rhnh + rh−1nh−1 +··· + r1n + r0. Osservazione 1. Per comodit´ a, invece di usare l’espressione (1), si scrive: (a)n = rhrh−1 . . . r1r0. che si dice scrittura del numero a in base n. Osservazione 2. Sia n∈ N∗, n̸=…