[Teoria liczb] Liczba nierozkładalna

[mol_ksiazkowy]

Rozpatrujemy sobie zbiór \(\displaystyle{ V_n}\) w oparciu o zadaną liczbę naturalną n większą od dwóch. \(\displaystyle{ V_n}\) tworzą liczby postaci \(\displaystyle{ kn+1}\) gdzie \(\displaystyle{ k=1,2,\ldots}\). Jeśli m należy do \(\displaystyle{ V_n}\), to mówimy, że m jest nierozkładalna wtedy i tylko wtedy, gdy nie istnieją w \(\displaystyle{ V_n}\) takie p i q, że \(\displaystyle{ m=pq}\). Wykaż, że w \(\displaystyle{ V_n}\) znajdzie się pewne r, że można je przedstawić na więcej niż jeden sposób w postaci iloczynu kilku elementów nierozkładalnych z \(\displaystyle{ V_n}\). Dwa rozkłady różniące się tylko porządkiem czynników uznajemy za tożsame.

[arek1357]

W każdym ciągu arytmetycznym jest nieskończenie wiele liczb pierwszych,

a iloczyn dowolnych dwóch wyrazów z naszego ciągu daje też wyraz należący do Vn

czyli wyrazy z tego zbioru są iloczynem wyrazów nierozkładalnych niekoniecznie wszystkich

[przemk20]

no to tak, wezmy sobie liczby
\(\displaystyle{ a_1 = \alpha, \ a_2 = n+\alpha \\
b_1 = r, \ b_2 = n+r \\
r \equiv \alpha^{\phi(n) - 1}\mod n \wedge r \in \lbrace 2,...,n-1 \rbrace \wedge (\alpha, n)=(r,n) = 1 \wedge \alpha >1 \\}\)
oczywiscie mamy
\(\displaystyle{ \alpha r \equiv 1 \mod n \\}\)
niech wreszcie
\(\displaystyle{ x = a_1 \cdot a_2 \cdot b_1 \cdot b_2 \\}\)
zauwazmy ze, liczba x spelnia warunki zadania, gdyz
\(\displaystyle{ x \equiv 1 \mod n \Rightarrow x \in V_n \\
a_1 b_1, \ a_2 b_2, \ a_1 b_2, \ a_2 b_1 \in V_n \\}\)
no i kazda z tych liczb jest nierozkladalna, co latwo pokazac, gdyz wtedy musialo by byc
\(\displaystyle{ (an+1)(bn+1) = a_i b_j, \ i,j \in\lbrace 1, 2 \rbrace, \ a,b \in N \\}\)
Pozdrawiam

[Sylwek]

przemk20, n nie musi być nieparzyste. Zamiast tego można zastąpić wszędzie dwójkę przez \(\displaystyle{ \alpha}\), przy czym jest to dowolna liczba pierwsza względnie pierwsza z n. Ale czy wówczas każda z liczb \(\displaystyle{ a_ib_j}\), \(\displaystyle{ i,j \in \{1, 2 \}}\) jest nierozkładalna?

[przemk20]

no tak, a juz myslalem ze tak latwo pojdzie... ;/
Heh no to inaczej,
Lemat
niech \(\displaystyle{ n \geq 3}\) Pokaze ze liczb pierwszych \(\displaystyle{ p \not\equiv 1 \mod n}\) jest nieskonczenie wiele, zalozmy ze jest przeciwnie, niech \(\displaystyle{ N=\prod p_i \not\equiv \mod n}\) bedzie iloczynem ich wszystkich, dla \(\displaystyle{ N \not\equiv -1 \mod n}\) widzimy, ze istnieje liczba pierwsza \(\displaystyle{ p \neq\equiv 1 \mod n}\) t. ze \(\displaystyle{ p | (N+1)}\) a ze \(\displaystyle{ p_i | N}\) to \(\displaystyle{ p \neq p_i}\) i dochodzimy do sprzecznosci
dla \(\displaystyle{ N \equiv -1 \mod n \wedge n \neq 3}\) wezmy \(\displaystyle{ N-1 \not\equiv \mod 3}\)
i podobnie jak poprzednio dochodzimy do sprzecznosci, zas dla \(\displaystyle{ n = 3}\) bierzemy \(\displaystyle{ N+3}\) gdyz \(\displaystyle{ p_i \neq 3}\) i znow mamy sprzecznosc...
... czyli lemat zostal dowiedziony
Z lematu i z zasady szufladkowej dirichleta wynika, ze istnieje pewna liczba \(\displaystyle{ \alpha_n \in \lbrace 2,3,...,n-1 \rbrace}\) t. ze dla dowolnie wielu liczb pierwszych \(\displaystyle{ p}\) zachodzi \(\displaystyle{ p \equiv \alpha_n \mod n}\)
niech \(\displaystyle{ k_n}\) bedzie najmniejsza liczba taka, ze \(\displaystyle{ \alpha_n^{k_n} \equiv 1 \mod n, \ k_n \in \lbrace 2,3,...,\phi(n) \rbrace}\)
niech \(\displaystyle{ A_n}\) bedzie zbiorem zlozonym z \(\displaystyle{ m \cdot k_n}\) elementow (gdzie \(\displaystyle{ m \geq 2}\) ) t. ze
\(\displaystyle{ a \in A_n \iff a \equiv \alpha_n \mod n \\}\)
zauwazmy ze:
\(\displaystyle{ \forall X \subset A_n \wedge |X| < k_n \prod_{p \in X} p = \prod X \not\equiv 1 \mod n}\)
innymi, slowy jest to ioczyn nierozkladalny w \(\displaystyle{ V_n}\)
zas \(\displaystyle{ \prod A_n \equiv 1 \mod n}\)
wezmy sobie teraz dowolne zbiory \(\displaystyle{ X_1,..., X_m, Y_1,..., Y_m}\) t. ze
\(\displaystyle{ X_i, Y_i \subset A_n \ \wedge \ |X_1|=|Y_i| = k_n \wedge \\ \bigcup X_i = \bigcup Y_i = A_n \ \wedge X_i \cap X_j = Y_i \cap Y_j \ \emptyset \ \wedge Y_i \neq X_i \\
j<i \in \lbrace 1,2,...,m \rbrace \\}\)
sa to po prostu pewne dwie rozne rodziny rozlacznych \(\displaystyle{ k_n}\) elementowych podzbiorow,
widzimy ze
\(\displaystyle{ \prod X_i = \prod Y_i \equiv 1 \mod n \\}\)
i ze liczba \(\displaystyle{ \prod A_n}\) jest szukana liczba o padanej wlasnosci....
uff
Pozdrawiam

-- 28 stycznia 2009, 14:40 --

I co teraz lepiej

[andkom]

Strasznie skomplikowane. Aż nie miałem cierpliwości przeczytać.
Zaproponuję coś innego:

Niech \(\displaystyle{ r=(4n^3-12n^2+13n-6)n+1}\)
Wówczas
\(\displaystyle{ r=((n-2)n+1)\cdot((4n-4)n+1)}\)
oraz
\(\displaystyle{ r=((2n-3)n+1)\cdot((2n-3)n+1)}\)
Rozkłady te są różne, bo dla n>2 mamy
\(\displaystyle{ (n-2)n+1<(2n-3)n+1<(4n-4)n+1}\)
Czy liczby występujące w tych rozkładach są nierozkładalne? Prosty rachunek pokazuje, że tak, jeśli tylko \(\displaystyle{ n\ne5}\) i \(\displaystyle{ n\ne8}\). Natomiast dla n=5 mamy
\(\displaystyle{ 16\cdot81=1296=6\cdot6\cdot6\cdot6}\)
a dla n=8 mamy
\(\displaystyle{ 49\cdot9\cdot25=11025=105\cdot105}\)

Można też pokazać, że dla \(\displaystyle{ n\not\in\{2,3,4,5,7,9,11,14,19\}}\) liczbę \(\displaystyle{ r=(24n^3-50n^2+35n-10)n+1}\) można przedstawić w postaci iloczynu liczb nierozkładalnych na co najmniej trzy różne sposoby:
\(\displaystyle{ r=((4n-5)n+1)\cdot((6n-5)n+1)\\r=((3n-4)n+1)\cdot((8n-6)n+1)\\r=((2n-3)n+1)\cdot((12n-7)n+1)}\)
Przypadkami \(\displaystyle{ n\in\{3,4,5,7,9,11,14,19\}}\) należy wówczas zająć się oddzielnie, czego robić mi się nie chce.

[przemk20]

A nie dziwie ci sie, ale osoba która zaklada temat to wypadało by żeby przeczytała ,
Pozrawiam