/******************************************************************************/
/* */
/* CHECK PTH POWER W.R.T. RELATIONSHIP FOR P=3 */
/* 12/14/13 (dkc) */
/* */
/* This program determines if q is congruent to the pth power of an integer */
/* (in the field K) modulo a+xb when q is a pth power w.r.t. [(a^p+b^p)/ */
/* (a+b)]. Small (a, b) values are checked. */
/* */
/*****************************************************************************/
#include <stdio.h>
int input[102+482]={
0x590013, // q=5, q divides a, b, a-b, or a+b, duplicated prime factors of [(a^p+b^p)/(a+b)]
0x4d0020,
0x350011,
0x170016,
0x640043, // q=11, q divides a-b or a+b
0x64002b,
0x640001,
0x620059,
0x620041,
0x620017,
0x620001,
0x610040,
0x61001f,
0x610014,
0x61000d,
0x5f0004,
0x5e003d,
0x5e0031,
0x5e0005,
0x5c001d,
0x5c0007,
0x5b0055,
0x5b0050,
0x5b003a,
0x5b0019,
0x5b0008,
0x590041,
0x590038,
0x590017,
0x59000a,
0x560035,
0x55003a,
0x530047,
0x53003d,
0x530026,
0x52003d,
0x520031,
0x520011,
0x500029,
0x500013,
0x4f0040,
0x4f002e,
0x4f0002,
0x4c002b,
0x4c0001,
0x490046,
0x49003e,
0x490028,
0x49001a,
0x47001c,
0x46001d,
0x440023,
0x44001f,
0x44000d,
0x43002b,
0x430020,
0x430017,
0x43000a,
0x430001,
0x410038,
0x41002b,
0x410020,
0x410017,
0x400035,
0x40000d,
0x3e003b,
0x3e001d,
0x3d001c,
0x3d0010,
0x3b0028,
0x3b001a,
0x3b0004,
0x3a0019,
0x3a0013,
0x38002b,
0x380017,
0x35002e,
0x350023,
0x350002,
0x34002f,
0x340019,
0x320031,
0x310010,
0x310005,
0x2f000e,
0x2e0023,
0x2b0022,
0x29000e,
0x280025,
0x280007,
0x260011,
0x260005,
0x25001a,
0x250007,
0x250004,
0x230002,
0x220001,
0x200017,
0x1f000d,
0x1d0007,
0x1c0011,
0x110005,
0x640051, // q=7
0x64004f,
0x64003f,
0x64003d,
0x640027,
0x640025,
0x640015,
0x64001a,
0x63005f,
0x63004a,
0x630019,
0x630004,
0x620055,
0x62000d,
0x61005c,
0x610055,
0x610054,
0x610053,
0x610050,
0x61004b,
0x610040,
0x610036,
0x61002b,
0x610021,
0x610016,
0x610011,
0x61000e,
0x61000d,
0x61000c,
0x610005,
0x600037,
0x600029,
0x5f005b,
0x5f0054,
0x5f004e,
0x5f0043,
0x5f0040,
0x5f001f,
0x5f001c,
0x5f0011,
0x5f000b,
0x5f0004,
0x5e0043,
0x5e003f,
0x5e001f,
0x5e001b,
0x5d0047,
0x5d0040,
0x5d001d,
0x5d0016,
0x5c0053,
0x5c0047,
0x5c003f,
0x5c0033,
0x5c0029,
0x5c001d,
0x5c0015,
0x5c0009,
0x5b0056,
0x5b0044,
0x5b003b,
0x5b0020,
0x5b0017,
0x5b0005,
0x5a0049,
0x5a003b,
0x5a001f,
0x5a0011,
0x59004c,
0x590042,
0x590041,
0x590034,
0x59002f,
0x59002a,
0x590025,
0x590018,
0x590017,
0x59000d,
0x580043,
0x580015,
0x570052,
0x570044,
0x57002f,
0x570028,
0x570013,
0x570005,
0x560051,
0x56003f,
0x56002f,
0x560027,
0x560017,
0x560005,
0x55004a,
0x550048,
0x550040,
0x55003f,
0x55002b,
0x55002a,
0x550016,
0x550015,
0x55000d,
0x55000b,
0x540053,
0x54004f,
0x540047,
0x540041,
0x54003d,
0x54003b,
0x540035,
0x54001f,
0x540019,
0x540017,
0x540013,
0x54000d,
0x540005,
0x540001,
0x53004b,
0x530049,
0x530047,
0x530036,
0x530031,
0x53002b,
0x53002a,
0x530029,
0x530028,
0x530022,
0x53001d,
0x53000c,
0x53000a,
0x530008,
0x52003f,
0x52003d,
0x52002d,
0x520025,
0x520015,
0x520013,
0x51004f,
0x510041,
0x51003a,
0x51002c,
0x510025,
0x510017,
0x510010,
0x510002,
0x500045,
0x50003f,
0x500035,
0x50001b,
0x500011,
0x50000b,
0x4f004d,
0x4f0041,
0x4f003f,
0x4f003c,
0x4f003a,
0x4f002f,
0x4f0020,
0x4f0015,
0x4f0013,
0x4f0010,
0x4f000e,
0x4f0002,
0x4e0043,
0x4e0035,
0x4e0019,
0x4e000b,
0x4d0034,
0x4d002b,
0x4d0022,
0x4d0019,
0x4c004b,
0x4c003f,
0x4c0037,
0x4c002b,
0x4c0029,
0x4c0023,
0x4c0021,
0x4c0015,
0x4c000d,
0x4c0001,
0x4b0029,
0x4b0022,
0x4a003f,
0x4a003b,
0x4a0039,
0x4a0035,
0x4a0015,
0x4a0011,
0x4a000f,
0x4a000b,
0x490044,
0x490038,
0x490035,
0x490034,
0x490030,
0x49002a,
0x49001f,
0x490019,
0x490015,
0x490014,
0x490011,
0x490005,
0x480047,
0x480001,
0x470046,
0x470040,
0x47003e,
0x470037,
0x470033,
0x47002a,
0x47001d,
0x470014,
0x470010,
0x470009,
0x470007,
0x470001,
0x450034,
0x450026,
0x45001f,
0x450011,
0x44002f,
0x440015,
0x430041,
0x43003f,
0x430039,
0x430034,
0x43002a,
0x430024,
0x430023,
0x430020,
0x43001f,
0x430019,
0x43000f,
0x43000a,
0x430004,
0x430002,
0x42003d,
0x42002f,
0x420013,
0x420005,
0x410040,
0x41003f,
0x41003d,
0x41002c,
0x41002a,
0x410017,
0x410015,
0x410004,
0x410002,
0x410001,
0x400033,
0x40000d,
0x3f003e,
0x3f003d,
0x3f003b,
0x3f0037,
0x3f0035,
0x3f0032,
0x3f002f,
0x3f002e,
0x3f002b,
0x3f0029,
0x3f0028,
0x3f0026,
0x3f0022,
0x3f001d,
0x3f0019,
0x3f0017,
0x3f0016,
0x3f0014,
0x3f0011,
0x3f0010,
0x3f000d,
0x3f000a,
0x3f0008,
0x3f0004,
0x3f0002,
0x3f0001,
0x3e0037,
0x3e0029,
0x3e0021,
0x3e001d,
0x3e0015,
0x3e0007,
0x3d003b,
0x3d003a,
0x3d002f,
0x3d002d,
0x3d0025,
0x3d0018,
0x3d0010,
0x3d000e,
0x3d0003,
0x3d0002,
0x3c0025,
0x3c0017,
0x3b0037,
0x3b0035,
0x3b0030,
0x3b002a,
0x3b0026,
0x3b0020,
0x3b001b,
0x3b0015,
0x3b0011,
0x3b000b,
0x3b0006,
0x3b0004,
0x3a0035,
0x3a0023,
0x3a0017,
0x3a0005,
0x390035,
0x390004,
0x380025,
0x380013,
0x370036,
0x37002f,
0x370022,
0x370015,
0x370008,
0x370001,
0x360029,
0x36000d,
0x35002e,
0x35002a,
0x350026,
0x350020,
0x350015,
0x35000f,
0x35000b,
0x350007,
0x340029,
0x34001f,
0x34001b,
0x340019,
0x340015,
0x34000b,
0x330032,
0x330001,
0x320029,
0x320025,
0x32000d,
0x320009,
0x31002f,
0x310026,
0x31001d,
0x310014,
0x31000b,
0x310002,
0x30001f,
0x300011,
0x2f002a,
0x2f001f,
0x2f001a,
0x2f0018,
0x2f0017,
0x2f0015,
0x2f0010,
0x2f0005,
0x2e001d,
0x2e0011,
0x2d001a,
0x2d0013,
0x2c0027,
0x2c0019,
0x2c0017,
0x2c0015,
0x2c0013,
0x2c0005,
0x2b0022,
0x2b001e,
0x2b0017,
0x2b0016,
0x2b0015,
0x2b0014,
0x2b000d,
0x2b0009,
0x2a0029,
0x2a0025,
0x2a001f,
0x2a001d,
0x2a0017,
0x2a0013,
0x2a000d,
0x2a000b,
0x2a0005,
0x2a0001,
0x29001c,
0x290016,
0x290013,
0x29000d,
0x280025,
0x280015,
0x280013,
0x280003,
0x270025,
0x270017,
0x270010,
0x270002,
0x260019,
0x260015,
0x260011,
0x26000d,
0x25001a,
0x250015,
0x250010,
0x25000b,
0x240019,
0x24000b,
0x23001f,
0x230016,
0x23000d,
0x230004,
0x220021,
0x22001d,
0x220015,
0x22000d,
0x220005,
0x220001,
0x210014,
0x21000d,
0x20001f,
0x200011,
0x20000f,
0x200001,
0x1f001b,
0x1f0019,
0x1f0015,
0x1f000a,
0x1f0006,
0x1f0004,
0x1d0015,
0x1d0014,
0x1d0009,
0x1d0008,
0x1c0017,
0x1c0005,
0x1a0017,
0x1a0015,
0x1a0013,
0x1a0007,
0x1a0005,
0x1a0003,
0x190015,
0x19000e,
0x19000b,
0x190004,
0x170015,
0x170012,
0x170005,
0x170002,
0x160015,
0x16000d,
0x160009,
0x160001,
0x150014,
0x150011,
0x150010,
0x15000d,
0x15000b,
0x15000a,
0x150008,
0x150005,
0x150004,
0x150001,
0x130010,
0x130003,
0x11000b,
0x11000a,
0x110007,
0x110006,
0xf000b,
0xf0004,
0xd000c,
0xd0001,
0x90008,
0x90001,
0x80007,
0x80001,
0x50003,
0x50002};
int main () {
int f,g,h,i,j,k,limit,limit1;
int A[2],T[2],U[2],temp,t,q;
FILE *Outfp;
Outfp = fopen("ppwrt.dat","w");
limit1=50;
limit=1500;
for (k=0; k<584; k++) {
A[0]=input[k]>>16;
A[1]=input[k]&0xffff;
if (k<4)
q=5;
else {
if (k<102)
q=11;
else
q=7;
}
if (A[0]>30)
continue;
printf("A=%d %d \n",A[0],A[1]);
for (h=0; h<limit1; h++) {
for (i=0; i<limit1; i++) {
U[0]=h;
U[1]=i;
for (j=1; j<3; j++) { // compute cube of an integer
t=U[1]*i;
temp=U[0]*h-t;
U[1]=U[0]*i+U[1]*h-t;
U[0]=temp;
}
U[0]=U[0]-q; // subtract q from cube
for (f=0; f<limit; f++) { // check if equals (A[0],A[1]) times integer
for (g=0; g<limit; g++) {
T[0]=f;
T[1]=g;
t=T[1]*A[1];
temp=T[0]*A[0]-t;
T[1]=T[0]*A[1]+T[1]*A[0]-t;
T[0]=temp;
if ((T[0]==U[0])&&(T[1]==U[1])) {
printf("q=%d, i=(%d %d), j=(%d %d), i cubed=(%d %d) \n",q,h,i,f,g,U[0]+q,U[1]);
goto askip;
}
}
}
}
}
askip:
A[0]=0;
}
fclose(Outfp);
return(0);
}