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

#1

Να βρεθεί φυσικός αριθμός ο οποίος αν διαιρεθεί με το

δίνει υπόλοιπο

, με το

δίνει υπόλοιπο

, με το

, δίνει υπόλοιπο

, ..(κλπ)... , με το

, δίνει υπόλοιπο

, ενώ διαιρείται ακριβώς με το

.

#2

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

#3

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

Καλησπέρα Δημήτρη. Εΰχαριστώ για την άμεση απάντηση.

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

Αφού ο

, διαιρούμενος με το $\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}$ .

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

#4

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

Όντως είναι ο ελάχιστος. Μπορούμε να τους βρούμε όλους ως εξής:

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

$\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$ .

Υπάρχει μέθοδος για να υπολογίσουμε το

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

Μετά, ψάχνουμε να βρούμε δύο ακεραίους m,n

ώστε

. Τέτοιο ζεύγος μπορεί να βρεθεί τρέχοντας τον Ευκλείδιο αλγόριθμο ανάποδα. Βρίσκουμε ότι τα 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$ το οποίο είναι και η λύση του συστήματος.

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

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

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

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

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

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