MEMERIKSA APAKAH SEBUAH BILANGAN ADALAH KUADRAT?

Apakah metode yang paling efisien untuk menentukan apakah sebuah bilangan bulat Nyang diberikan
adalah bilangan kuadrat (bilangan persegi). Salah satu pendekatan akan untuk memeriksa apakah N adalah modulo persegi nomor kecil beberapa yang mungkin dapat dilakukan lebih mudah daripada penggalian akar kuadrat penuh. Untuk itu Misalnya, jika kita ingin mengetahui apakah bilangan

              N = 371930958274059827465211239444089

adalah persegi, pertama kita dapat memeriksa dua digit terakhir  untuk melihat jika dua digit terakhir adalah salah satu kuadrat dua puluh dua kemungkinan (mod 100), sepuluh yang jelas {00,01,04,09, .., 81} dan sisa dua belas yang} {21,24,29,41,44,56,61,69,76,84,89,96. Kemungkinan dari dipilih secara acak non-persegi bulat lulus tes ini hanya 22/100. Kemudian, mengambil keuntungan dari fakta bahwa 999999 = 3 * 3 * 7 * 11 * 13 * 37, kita  dapat memeriksa untuk melihat jika N adalah modulo persegi masing-masing bilangan prima dengan hanya membentuk jumlah digit N diambil 6 pada suatu waktu:

                            444089
                            211239
                            827465
                            274059
                            930958
                               371
                           -------
          Jumlah  = 2688181

Kuadrat (mod 9) adalah {0,1,4,7}, dan Jumlah  ini kongruen dengan 7 (mod 9), jadi kita masih tidak bisa yakin itu kuadrat atau bukannya. Namun, karena kongruen dengan 6 (mod 7), sedangkan bilangan kuadrat (mod 7) adalah {0,1,2,4}, sehingga N tidak akan kuadrat  (persegi). Secara umum, diharapkan probabilitas yang dipilih secara acak non-persegi bilangan bulat lulus "uji kuadrat" relatif terhadap (2 ^ 2) (5 ^ 2), 3 ^ 2, 7,
11, 13, dan 37 menjadi sekitar

                22 4 4 6 7 19
           P = ---- --- --- ---- ---- ---- = 0,0084
               100 9 7 11 13 37

sehingga akan menangkap lebih dari 99% dari non-kotak. Atau, kita bisa mengambil keuntungan dari fakta bahwa 1001 = 7 * 11 * 13 dan sebagainya 1000 = -1 (mod 7 * 11 * 13). Jadi, jika kita mengambil angka dari N dalam kelompok 3, dan bergantian menambah dan mengurangi mereka, kita dengan mudah dapat memeriksa kuadrat modulo 7, 11, dan 13. Jadi pendekatan tercepat mungkin untuk pertama memeriksa desimal dua terakhir digit untuk kuadrat (mod 100), kemudian menambahkan satu digit pada suatu waktu dan memeriksa jumlah untuk kuadrat (mod 9), dan kemudian menjumlahkan angka tiga sekaligus (dengan bolak tanda-tanda) dan memeriksa jumlah untuk kuadrat modulo 7, 11, dan 13. Ini akan menangkap lebih dari 98% dari bilangan bukan kuadrat (persegi)

sumber : http://www.mathpages.com/home/kmath265.htm.