olimpiadi di Bulgaria
olimpiadi di Bulgaria
Dimostrare che per ogni intero positivo n, 7 è un divisore di $ 3^n+n^3 $ se è solo se 7 è un divisore di $ 3^nn^3+1 $
Appassionatamente BTA 197!
intanto notiamo le congruenze di n^3 modulo 7
se $ \displaystyle n \equiv 0 $ , $ \displaystyle n^3 \equiv 0 $
se $ \displaystyle n \equiv 1 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 2 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 3 $ , $ \displaystyle n^3 \equiv 6 $
se $ \displaystyle n \equiv 4 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 5 $ , $ \displaystyle n^3 \equiv 6 $
se $ \displaystyle n \equiv 6 $ , $ \displaystyle n^3 \equiv 6 $
nel primo caso per il piccolo teorema di fermat nessuno dei 2 è divisibile per 7, gli altri casi sono con residui 1 e 6 quindi
se $ \displaystyle n^3 \equiv 1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^n \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv -1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 + 1 \equiv 0 $ $ $$(mod 7)$$ $
oppure
se $ \displaystyle n^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^n \equiv 1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv -1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 + 1 \equiv 0 $ $ $$(mod 7)$$ $
Spero si capisca avevo poco tempo per scrivere...il solo si potrebbe dimostrare similmente credo, ma ora non ho tempo per farlo
bye
se $ \displaystyle n \equiv 0 $ , $ \displaystyle n^3 \equiv 0 $
se $ \displaystyle n \equiv 1 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 2 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 3 $ , $ \displaystyle n^3 \equiv 6 $
se $ \displaystyle n \equiv 4 $ , $ \displaystyle n^3 \equiv 1 $
se $ \displaystyle n \equiv 5 $ , $ \displaystyle n^3 \equiv 6 $
se $ \displaystyle n \equiv 6 $ , $ \displaystyle n^3 \equiv 6 $
nel primo caso per il piccolo teorema di fermat nessuno dei 2 è divisibile per 7, gli altri casi sono con residui 1 e 6 quindi
se $ \displaystyle n^3 \equiv 1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^n \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv -1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 + 1 \equiv 0 $ $ $$(mod 7)$$ $
oppure
se $ \displaystyle n^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^n \equiv 1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv 6 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 \equiv -1 $ $ $$(mod 7)$$ $
$ \displaystyle 3^nn^3 + 1 \equiv 0 $ $ $$(mod 7)$$ $
Spero si capisca avevo poco tempo per scrivere...il solo si potrebbe dimostrare similmente credo, ma ora non ho tempo per farlo
bye
[b]Membro Club Nostalgici[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Soluzione un po' più veloce...
se n è un multiplo di 7, allora nessuno dei due è divisibile per 7. Supponiamo n non nullo modulo 7:
$ ~ 7 \mid 3^n+n^3 \Leftrightarrow $
$ ~ 3^n \equiv -n^3 \pmod 7 \Leftrightarrow $
$ ~ 3^n n^3 \equiv -n^6 \pmod 7 \Leftrightarrow $
$ ~ 3^nn^3 \equiv -1 \pmod 7 \Leftrightarrow $ (per Fermat)
$ ~ 7 \mid 3^nn^3 + 1 $
se n è un multiplo di 7, allora nessuno dei due è divisibile per 7. Supponiamo n non nullo modulo 7:
$ ~ 7 \mid 3^n+n^3 \Leftrightarrow $
$ ~ 3^n \equiv -n^3 \pmod 7 \Leftrightarrow $
$ ~ 3^n n^3 \equiv -n^6 \pmod 7 \Leftrightarrow $
$ ~ 3^nn^3 \equiv -1 \pmod 7 \Leftrightarrow $ (per Fermat)
$ ~ 7 \mid 3^nn^3 + 1 $
Il fatto è che il $ ~ 3^n $ in effetti centra poco. Non ho neanche notato che la mia dimostrazione implica che, se f è una funzione da N a Z tale che $ ~ 7 \nmid f(7k) $, allora:
$ ~ 7 \mid f(n)+n^3 \Leftrightarrow 7 \mid f(n)n^3 + 1 $
Questo spiega perchè (nella mia dimostrazione) me ne frego altamente che $ ~ 3^n $ modulo 7 ha un periodo lungo 6.
$ ~ 7 \mid f(n)+n^3 \Leftrightarrow 7 \mid f(n)n^3 + 1 $
Questo spiega perchè (nella mia dimostrazione) me ne frego altamente che $ ~ 3^n $ modulo 7 ha un periodo lungo 6.
Anche nella mia si vede che il $ \displaystyle 3^n $ può essere qualsiasi cosa tranne che essere equivalente a 0 mod 7
[b]Membro Club Nostalgici[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]