I'm new to this, I tried writing a code compare Guass' Lemma and Euler's Criteria for finding the Legendre symbol for any 2 numbers, they both work perfectly fine for small numbers (less than 5 digits) but at some point above that they always give different answers. Can anyone out there point out why at least one of the methods fails with large numbers? As an example, LS(n<20510/1047290) is right but LS(n>20511/104729) gives different answers. Thank you.

use strict;
use warnings;
use integer;
use Time::HiRes;
use Benchmark;

my ($qa,$a,$b,$p,$k,$t,$c,$z,$w,$n,$r);
my ($start_run,$end_run,$run_time);
my ($start_rune,$end_rune,$run_timee);

print "Find Legendre symbol of:";
$qa=<>;
print "modulo:";
$p=<>;
#Gauss
$start_run = time();
$c=($p+1)/2;
$n=0;
$k=1;
while($k < $c){
    $r=$k*$qa;
    $r= $r % $p;
    if ($r > $p/2)    {
        $n++;
    
        }    
    $k++;
}
if($n % 2){
    $w=-1;
}
else{
    $w=1;
}
$end_run = time();
$run_time = $end_run - $start_run;

#Euler
$start_rune = time();
$c=($p-1)/2;
$t=1;
$k=$qa;
while ($t ne $c){
    $k=$k*$qa; 
    $t++;
    $k=$k % $p;
}
if($k == 1){
    $z=1;
}  
else{
    $z=-1;
}
$end_rune = time();
$run_timee = $end_run - $start_run;
if($w ne $z){
    print "algorithms disagree for $qa mod $p \n";
    exit;
}
if($z == 1){
    print "quad res \n";
}
else{
    print "not quad res \n";
}
print "Running time for Guass Lemma: $run_time seconds\n";
print "Running time for Eulers Criterion: $run_timee seconds\n";
[download]

EDIT: edited code so compiles