Bölünebilme

1≤n≤256 olmak üzere 19^n2+8n+135+1 sayısının 257 ile bölünmesini sağlayan kaç n pozitif tam sayısı vardır ?

257 fermat asalı olduğundan 19 un ilkel kök olması için gerek ve yeter koşul quadratic residue olmamasıdır. yani bi sayının karesi olmaması

257 4k+1 şekilli olduğundan
a²≡19 (mod257) nin çözümünün olması için gerek ve yeter şart
a²≡257 (mod19) un çözümünün olmasıdır
a²=257=10 (mod19)
a için 1,2,...,9 denenirse bunun çözümü olmadığı ve dolayısıyla 19 sayısının 257 modunda ilkel kök olduğu yani ilk defa 19¹²⁸≡-1 (mod257) olduğu anlaşılır

19^n²+8n+135≡-1 (mod257) olmasını istiyoruz
n²+8n+135=256k+128 formundadır

n²+8n+7=256k
(n+1).(n+7)=256k , çarpanlar arasında 6 fark olduğundan ve n tek sayı olacağından birinden tek bir tane 2 çarpanı gelir diğerinden de 128 çarpanı gelmelidir.
n+1=256 → n=255
n+1=128 → n=127
n+7=256 → n=249
n+7=128 → n=121
isteneni sağlayan n sayıları olmalı.

Teşekkür ederim ama ben pek anlayamadım.
İlkel kök ve quadratic residue ne demek? Neden a²≡19 (mod257) çözümünün olmasını istiyoruz ve neden bunun çözümünün olması a²≡257 (mod19) in çözümünün olmasına bağlı? 19¹²⁸≡-1 (mod257) olduğunu nasıl bulduk ?

ilkel kök : herhangi bir n modunda bir r sayısının ilkel kök olması demek , o modda n ile aralarında asal her sayının r nin bir kuvveti olarak yazılabilmesi demek. özel olarak mod asalsa r nin kuvvetlerinin tüm kalanlar sınıfını oluşturması demek.
örneğin 7 modunda 2 ilkel kök değildir çünkü tüm kalanlar sınıfını oluşturmaz, kuvvet 6 olmadan henüz 3 ken 2³=1 (mod7) olmaktadır.
yine 7 modunda 3 bir ilkel köktür çünkü 3² veya 3³ 1 e denk değil. yani ilk defa 3⁶ da 1 e ulaşılıyor (bunda ulaşılması fermata göre kesin zaten - uzatıyorum ama olsun)
3 ün ilk defa 1 olduğu nokta için 6 nın bölenlerine bakıyoruz.

quadratic residue: a²≡b (modn) ifadesinde b n modunda bir quadratic residuedür. bir sayının karesi olan sayı işte (ya da "kare kalan" , Türkçe'de ne diyoruz bilmiyorum). mesela 5 modunda 4 bir kareyken , 2 ve 3 değildir

quadratic reciprocity theorem: (bunun da Türkçesi "karesel ters/çevirme teoremi" heralde )
p ve q asalken
a²=p (modq) olan a bulunması için gerek ve yeter şart

q=4k+1 ise b²=q (modp)
q=4k+3 ise b²=-q (modp) olan b sayısının bulunmasıdır.

------------

şimdi soruya gelirsek 19 un ilkel kök olmasını bulmayı amaçladık. burada 257 fermat asalı olduğundan 19 un sadece 2 nin kuvvetleri olan kuvvetlerine bakacağımızdan 19 un ilkel kök olması ancak ve ancak quadratic residue olmamasıyla mümkündür.

yukarıdaki teoreme göre de
a²=19 (mod257) nin çözümü olmasın istiyorsak
b²=257=10 (mod19) un çözümü olmamalıdır , ki yoktur zaten. sonuçta 19 ilkel köktür
19 un kuvvetleri 257 modundaki tüm kalanları oluşturur yani ilk defa 1 e 19²⁵⁶ da ve dolayısıyla ilk defa -1 e 19¹²⁸ de ulaşılır.

gerisi zaten yeterince açık olmalı. kafamdakileri ancak bu kadar toparlayabildim, anlaşılmayan yer varsa sorabilirsin bazı yerlerde yanlış/eksik yazmış olabilirim .

şimdi evden çıkmam lazım ve soru kafama takıldı, bugün uygun bi zamanda tekrar bakayım, muhtemelen eksik bişey yok ama olsun.

Anladım çok teşekkür ederim Peki 19'un mod 257'de ilkel kök olması için quadratic residue olmaması lazım dedik ya. Bu kural sadece asal olunca mı geçerli ?

hayır bu 257 ya da benzeri sayılar için geçerli (fermat asalları vs)

şöyle düşünelim 19 bi sayının karesi olabilse atıyorum x²=19 , ardından x^256=1 olduğundan 19^128=1 olması kesinleşir bu da 19 un ilkel kök olmamasıdır.
yani mesele 256 nın sadece 2 lerden oluşması.

ayrıca sorunun çözümüne salim kafayla bi daha baktım da sıkıntı yok, bu haliyle bana göre doğru. 4 tane n sayısı bulunabiliyor.

fermat asalı ne demek ?

Fermat sayıları: Fermat sayıları - Vikipedi
İyi günler.

Bir de şöyle bir soru var. Bakar mısınız ? 7²ⁿ+1 sayısının 1201'e bölünmesini sağlayan kaç n pozitif tam sayısı vardır ?
Teşekkür ederim