Układ kongruencji dający wzory na dzielniki liczby

W ostatnim poście napisałem 'wzór na dzielniki'. Jest to raczej układ kongruencji, które są widoczne jako układ równań.

Postać wejściowa to palindrom [i,j,k,j,i]_p nad systemem pozycyjnym o podstawie p, który jest przedstawiony jako iloczyn dwu palindromów. W tym iloczynie wartości skrajne są znane, nieznane są tylko pozycje odpowiadające cyfrom dziesiątek liczb. 

Zatem dany jest iloczyn [a, x, a]_p * [b, y, b]_p , z niewiadomymi x, y. 

Konwertujemy palindrom na systemy o podstawach (p-1) oraz (p+1). Uzyskujemy w ten sposób nowe wielomiany, których współczynniki są blisko ze sobą związane. Niestety, przenoszenie między cyframi może się jeszcze zachować mimo próby jego uwzględnienia we współczynnikach stałych układu. Porównując teraz współczynniki (jako kombinacje liniowe i jako iloczyny) uzyskujemy wspomniany układ kongruencji. 

I to wszystko.  

Na przykładzie N = 8934053 = [15, x, 15]_{16} * [11, y, 11]_{16}

Jeden z palindromów to N = [165, 0, -7342, 0, 165]_{16}, inny N = [165, 3152, -57971, 3152, 165]_{16}. 

Mamy dodatkową stałą 4*165 = 660, oraz układ równań: 

N = [165, e, e+f, 2f, f] _{15} = [165, c, d-c, -2d, d]_{17}
e-c = 4*165 = 660  (co pochodzi z kombinacji liniowej (x,y) z (15,11))
c = 11x+15y-660
e = 11x+15y+660
d = xy -2*11x-2*15y+4*165 = g*h
f = xy+2*11x+2*15y+4*165 = (4*15-g)*(4*11-f)
g = 2*15-x
h = 2*11-y

W praktyce uzyskane współczynniki nie są zbyt miłe:
N = [165, 3812, -47525, -102674, -51337]_{15}
N = [165, 2492, -66437, 127890, -63945]_{17}

Dlatego jednak preferuję inne sposoby rozkładu... Nie jestem do końca pewien, czy potrafię rozwiązywać takie układy, czy palindrom początkowy nie ma tutaj znaczenia.

Wzór na dzielniki. przygotowanie postaci

 Już parę razy zastanawiałem się tutaj, czy istnieje wzór na dzielniki liczby. I teraz znalazłem postać, dla której istnieje układ równań, z którego można wyznaczyć dzielniki. 

W tym poście przedstawię ową specyficzną postać zapisu liczby. 

Palindromem nad postawą p nazywamy wielomian o współczynnikach całkowitych postaci 

a[n] * p^n+ ... + a[1] *p + a[0], 

w którym a[n] = a[0], a[n-1] = a[1], ... po zmianie oznaczeń (n = 2k+1, r naturalne, dla n parzystego dwa sąsiednie wyrazy w środku są równe) a[k+r]=a[k-r] , 

np. [7, 12, 18, -1, 18, 12, 7]_{16} to palindrom nad systemem szesnastkowym o długości 7 i wartości liczbowej N = 7*(16^6+1) + 12*(16^5+16) + 18*(16^4+16^2) - 1*16^3.  Palindrom tworzymy po prostu przenosząc od krajów wartości z cyfr do cyfr mniej znaczących kończąc w środku. Skaczemy od cyfr mało znaczących do dużo znaczących i na odwrót dopasowując wartości najpierw na pozycjach mniej znaczących.

Własności palindromu nad systemem p: 

- z dowolnej liczby całkowitej można uzyskać palindrom nieparzystej długości, palindrom parzystej długości udaje się wyznaczyć tylko wtedy, gdy wartość liczbowa jest podzielna przez p+1.

- skrajne współczynniki palindromu są wielokrotnościami reszty z dzielenia N przez p.

- cecha podzielności: wartość palindromu jest podzielna przez x, gdy wszystkie współczynniki palnidromu są wielokrotnościami x, np. [x, 3x, 0, 2x, 0, 2x, 0, 3x, x]_p; albo wspólny dzielnik wyraz skrajnego a[0] i p jest dzielnikiem N. 

- iloczyn palindromów jest palindromem. 

-  konwersja palindromu długości 3: [a, b, a] na sąsiedni system (p+1) lub (p-1) ma z dokładnością do znaku tylko dwa różne współczynniki [a, 2a+b, 2a+b]_{p-1} oraz [a, b-2a, 2a-b]_{p+1}. Konwersje niszczą zatem strukturę palindromu. 

- palindrom nie jest  jednoznacznie wyznaczony, niezmiennikiem palindromu długości 3 jest [a+p, b-p*p-1, a+p]_p = [a,b,a]_p . Najwięcej napotykanych palindromów jest nad systemem binarnym. np. skrajne o wyrazach dodatnich liczby nieparzystej to: pierwszy [1, (N-5)/2, 1]_2, w drugim mamy około (zależy od parzystości N) [floor(N/5), x, floor*N/5)]_2 , gdzie x ma jedną z wartości: 0, 1, 2, 3, 4 w zależności od N. Dla 8934053 mamy w ten sposób palindromy  o wyrazach dodatnich między [1, 4467024, 1]_2 oraz [1786809, 4, 1786809]_2. Ze wzrostem p palindromy są coraz rzadziej spotykane. 

Przechodzę do postaci liczby N. 

Tworzę palindrom długości 5 o takiej podstawie, by jego współczynniki były stosunkowo małe, a wyrazy skrajne były wielokrotnościami reszty z dzielenia przez p takimi, by wyraz skrajny a[0] = m*n \equiv (N%p) (mod p). Dobieram je tak, by 0<=m,n<p oraz p^2 | (N-mn). Oznacza to, że m, n są cyframi jedności dzielników liczby N zapisanymi w systemie p. 

np. N = 8934053 \equiv 5 (mod 16), oraz można tę wartość przedstawić jako palindromy 

N = [85, 85, 11773, 85, 85]_{16}

oraz 

N = [165, 0, -7342, 0, 165]_{16}

W tej drugiej postaci mamy odpowiednie wartości 165 = 15*11, zatem jest to iloczyn palindromów 

N = [15, x, 15]_{16} * [11, y, 11]_{16}

Mnożąc te palindromy uzyskujemy układ kongruencji, z których można poszukiwać zmiennych z oraz y. Ale jest to także układ wejściowy dla utworzenia układu równań, z których można wyznaczyć brakujące współczynniki dzielników... Zamierzam umieścić wkrótce...