Δέκα υπόλοιπα

Συντονιστής: nkatsipis

ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ
Επιμελητής
Δημοσιεύσεις: 4189
Εγγραφή: Τρί Αύγ 31, 2010 10:37 pm
Τοποθεσία: Ιστιαία Ευβοίας

Δέκα υπόλοιπα

#1

Μη αναγνωσμένη δημοσίευση από ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ » Τρί Οκτ 16, 2012 9:35 pm

Να βρεθεί φυσικός αριθμός ο οποίος αν διαιρεθεί με το 2 δίνει υπόλοιπο 1, με το 3 δίνει υπόλοιπο 2, με το 4, δίνει υπόλοιπο 3, ..(κλπ)... , με το 10, δίνει υπόλοιπο 9, ενώ διαιρείται ακριβώς με το 11.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7852
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: ΄Δέκα υπόλοιπα

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Οκτ 16, 2012 9:40 pm

Ο N = 10 \cdot (10!)-1 δουλεύει. Το μόνο που δεν είναι προφανές είναι η διαιρετότητα με το 11 η οποία έπεται από το θεώρημα του Wilson.


ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ
Επιμελητής
Δημοσιεύσεις: 4189
Εγγραφή: Τρί Αύγ 31, 2010 10:37 pm
Τοποθεσία: Ιστιαία Ευβοίας

Re: ΄Δέκα υπόλοιπα

#3

Μη αναγνωσμένη δημοσίευση από ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ » Τρί Οκτ 16, 2012 10:19 pm

Demetres έγραψε:Ο N = 10 \cdot (10!)-1 δουλεύει. Το μόνο που δεν είναι προφανές είναι η διαιρετότητα με το 11 η οποία έπεται από το θεώρημα του Wilson.
Καλησπέρα Δημήτρη. Εΰχαριστώ για την άμεση απάντηση.

Γράφω και μια ακόμα λύση, που έχω υπόψιν:

Αφού ο x , διαιρούμενος με το \displaystyle{10}, δίνει υπόλοιπο \displaystyle{9}, άρα ο \displaystyle{x+1} ,θα πρέπει να διαιρείται με το \displaystyle{10}.

Αφού ο \displaystyle{x}, διαιρούμενος με το \displaystyle{9}, δίνει υπόλοιπο \displaystyle{8}, άρα ο \displaystyle{x+1}, διαιρείται με το \displaystyle{9}

...........................
...........................
..........................

Aφού ο \displaystyle{x}, διαιρούμενος με το \displaystyle{2}, δίνει υπόλοιπο \displaystyle{1}, άρα ο \displaystyle{x+1}, διαιρείται με το \displaystyle{2}.

Αυτό σημαίνει, ότι ο αριθμός \displaystyle{x+1} διαιρείται ακριβώς με τους αριθμούς \displaystyle{2 , 3 , 4 , 5 , ... , 10}.

Το ΕΚΠ των πιο πάνω αριθμών, είναι το \displaystyle{2520}. Άρα ο \displaystyle{x+1}, θα είναι πολλαπλάσιο του \displaystyle{2520} και άρα ο ζητούμενος
αριθμός θα μπορεί να είναι ο \displaystyle{x=2519}. Παρατηρούμε ότι ο \displaystyle{2519}, διαιρείται ακριβώς με το \displaystyle{11}.

Συνεπως είναι ένας από τους αριθμούς που ζητάμε (και νομίζω ότι είναι και ο ελάχιστος).


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7852
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: ΄Δέκα υπόλοιπα

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Οκτ 07, 2016 11:52 am

ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ έγραψε: Συνεπως είναι ένας από τους αριθμούς που ζητάμε (και νομίζω ότι είναι και ο ελάχιστος).
Όντως είναι ο ελάχιστος. Μπορούμε να τους βρούμε όλους ως εξής:

Μας δίνονται οι ισοδυναμίες

\displaystyle{ x \equiv 1 \bmod 2}
\displaystyle{ x \equiv 2 \bmod 3}
\displaystyle{ \cdots}
\displaystyle{ x \equiv 9 \bmod 10}
\displaystyle{ x \equiv 0 \bmod 11}

Αυτές είναι ισοδύναμες με τις εξής:
\displaystyle{ x \equiv -1 \bmod 5}
\displaystyle{ x \equiv -1 \bmod 7}
\displaystyle{ x \equiv -1 \bmod 8}
\displaystyle{ x \equiv -1 \bmod 9}
\displaystyle{ x \equiv 0 \bmod 11}

[Η δεύτερη λίστα εμπεριέχεται στην πρώτη. Μπορούμε όμως να πάμε και ανάποδα. Π.χ. το x \equiv - 1 \bmod 8 δίνει και x \equiv -1 \equiv 1 \bmod 2. Μαζί με το x \equiv -1 \bmod 5 δίνει το x \equiv -1 \equiv 9 \bmod 10 κ.τ.λ.]

Επειδή τώρα τα 5,7,8,9,11 είναι πρώτοι μεταξύ τους, το Kινέζικο θεώρημα λέει ότι υπάρχει μοναδικό a \in \{1,2,\ldots,N\} ώστε x \equiv a \bmod N όπου N = 5 \cdot 7 \cdot 8 \cdot 9 \cdot 11 = 27720.

Υπάρχει μέθοδος για να υπολογίσουμε το a. Αρχικά μπορούμε να γλιτώσουμε αρκετές πράξεις παρατηρώντας ότι τα πιο πάνω είναι ισοδύναμα με
\displaystyle{ x \equiv -1 \bmod 2520}
\displaystyle{ x \equiv 0 \bmod 11}

Μετά, ψάχνουμε να βρούμε δύο ακεραίους m,n ώστε 2520m + 11n = 1. Τέτοιο ζεύγος μπορεί να βρεθεί τρέχοντας τον Ευκλείδιο αλγόριθμο ανάποδα. Βρίσκουμε ότι τα m=1,n=-229 δουλεύουν.

Επειδή όμως 2520m + 11n = 1, τότε το x = 0 \times 2520 m + (-1) \times 11n ικανοποιεί τις δύο ισοδυναμίες. Δηλαδή μπορούμε να πάρουμε a = 11 \times 229 = 2519.

Καταλήγουμε λοιπόν ότι x \equiv 2519 \bmod 27720 το οποίο είναι και η λύση του συστήματος.


Απάντηση

Επιστροφή σε “ΘΕΩΡΙΑ ΑΡΙΘΜΩΝ”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης