mersenneforum.org Self-gratification by a²+kb² forms "with ~10% FALSE STATEMENTS" (by author)
 Register FAQ Search Today's Posts Mark Forums Read

 2013-02-04, 02:19 #1 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 100111010012 Posts Self-gratification by a²+kb² forms "with ~10% FALSE STATEMENTS" (by author) In general: If two numbers are representable as a²+kb², for fixed k value, then their product is representable as a²+kb². (a²+kb²)(c²+kd²) = |ac+kbd|² + k|ad-bc|² (a²+kb²)(c²+kd²) = |ac-kbd|² + k|ad+bc|² We always assume that a, b are non-negative integers ≥ 0. Let p be a prime that can be written as a²+kb², then, if N is a non-negative integer that can be written as a²+kb², then p × N can be written as a²+kb² if N is a non-negative integer that cannot be written as a²+kb², then p × N cannot be written as a²+kb² Such prime representations by a²+kb² form are always unique - for fixed k value.
 2013-02-04, 02:22 #2 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts k = 1 Primes p of the form a²+b² : {1, 2} mod 4. if N is a non-negative integer that can be written as a²+b², then p × N can be written as a²+b² if N is a non-negative integer that cannot be written as a²+b², then p × N cannot be written as a²+b² N can be written as a²+b² if and only if - N has no prime factors congruent to {3} mod 4 to an odd power. k = 2 Primes p of the form a²+2b² : {1, 2, 3} mod 8. if N is a non-negative integer that can be written as a²+2b², then p × N can be written as a²+2b² if N is a non-negative integer that cannot be written as a²+2b², then p × N cannot be written as a²+2b² N can be written as a²+2b² if and only if - N has no prime factors congruent to {5, 7} mod 8 to an odd power. k = 3 Primes p of the form a²+3b² : {0, 1} mod 3. if N is a non-negative integer that can be written as a²+3b², then p × N can be written as a²+3b² if N is a non-negative integer that cannot be written as a²+3b², then p × N cannot be written as a²+3b² N can be written as a²+3b² if and only if - N has no prime factors congruent to {2} mod 3 to an odd power. k = 4 Primes p of the form a²+4b² : {1} mod 4. if N is a non-negative integer that can be written as a²+4b², then p × N can be written as a²+4b² if N is a non-negative integer that cannot be written as a²+4b², then p × N cannot be written as a²+4b² N can be written as a²+4b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {3} mod 4 to an odd power. k = 5 Primes p of the form a²+5b² : {1, 5, 9} mod 20. if N is a non-negative integer that can be written as a²+5b², then p × N can be written as a²+5b² if N is a non-negative integer that cannot be written as a²+5b², then p × N cannot be written as a²+5b² N can be written as a²+5b² if and only if - N has no prime factors congruent to {11, 13, 17, 19} mod 20 to an odd power. - Sum of exponents of {2, 3, 7} mod 20 prime factors of N is even. k = 6 Primes p of the form a²+6b² : {1, 7} mod 24. if N is a non-negative integer that can be written as a²+6b², then p × N can be written as a²+6b² if N is a non-negative integer that cannot be written as a²+6b², then p × N cannot be written as a²+6b² N can be written as a²+6b² if and only if - N has no prime factors congruent to {13, 17, 19, 23} mod 24 to an odd power. - Sum of exponents of {2, 3, 5, 11} mod 24 prime factors of N is even. k = 7 Primes p of the form a²+7b² : {1, 7, 9, 11} mod 14. if N is a non-negative integer that can be written as a²+7b², then p × N can be written as a²+7b² if N is a non-negative integer that cannot be written as a²+7b², then p × N cannot be written as a²+7b² N can be written as a²+7b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {3, 5, 13} mod 14 to an odd power. k = 8 Primes p of the form a²+8b² : {1} mod 8. if N is a non-negative integer that can be written as a²+8b², then p × N can be written as a²+8b² if N is a non-negative integer that cannot be written as a²+8b², then p × N cannot be written as a²+8b² N can be written as a²+8b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {5, 7} mod 8 to an odd power. - If N is odd, then the sum of exponents of {3} mod 8 prime factors of N is even. k = 9 Primes p of the form a²+9b² : {1} mod 12. if N is a non-negative integer that can be written as a²+9b², then p × N can be written as a²+9b² if N is a non-negative integer that cannot be written as a²+9b², then p × N cannot be written as a²+9b² N can be written as a²+9b² if and only if - N has no prime factors congruent to {3, 7, 11} mod 12 to an odd power. - If N is not a multiple of 3, then the sum of exponents of {2, 5} mod 12 prime factors of N is even. k = 10 Primes p of the form a²+10b² : {1, 9, 11, 19} mod 40. if N is a non-negative integer that can be written as a²+10b², then p × N can be written as a²+10b² if N is a non-negative integer that cannot be written as a²+10b², then p × N cannot be written as a²+10b² N can be written as a²+10b² if and only if - N has no prime factors congruent to {3, 17, 21, 27, 29, 31, 33, 39} mod 40 to an odd power. - Sum of exponents of {2, 5, 7, 13, 23, 37} mod 40 prime factors of N is even. Last fiddled with by Raman on 2013-02-04 at 02:25
 2013-02-04, 02:23 #3 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 100111010012 Posts k = 12 Primes p of the form a²+12b² : {1} mod 12. if N is a non-negative integer that can be written as a²+12b², then p × N can be written as a²+12b² if N is a non-negative integer that cannot be written as a²+12b², then p × N cannot be written as a²+12b² N can be written as a²+12b² if and only if - N has no prime factors congruent to {2, 5, 11} mod 12 to an odd power. - If N is odd, then the sum of exponents of {3, 7} mod 12 prime factors of N is even. k = 13 Primes p of the form a²+13b² : {1, 9, 13, 17, 25, 29, 49} mod 52. if N is a non-negative integer that can be written as a²+13b², then p × N can be written as a²+13b² if N is a non-negative integer that cannot be written as a²+13b², then p × N cannot be written as a²+13b² N can be written as a²+13b² if and only if - N has no prime factors congruent to {3, 5, 21, 23, 27, 33, 35, 37, 41, 43, 45, 51} mod 52 to an odd power. - Sum of exponents of {2, 7, 11, 15, 19, 31, 47} mod 52 prime factors of N is even. k = 15 Primes p of the form a²+15b² : {1, 4} mod 15. if N is a non-negative integer that can be written as a²+15b², then p × N can be written as a²+15b² if N is a non-negative integer that cannot be written as a²+15b², then p × N cannot be written as a²+15b² N can be written as a²+15b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {7, 11, 13, 14} mod 15 to an odd power. - Sum of exponents of {2, 3, 5, 8} mod 15 prime factors of N is even. k = 16 Edit: At the request of the author, please note that this is incorrect. A corrected version of this is stated below. Primes p of the form a²+16b² : {1} mod 8. if N is a non-negative integer that can be written as a²+16b², then p × N can be written as a²+16b² if N is a non-negative integer that cannot be written as a²+16b², then p × N cannot be written as a²+16b² N can be written as a²+16b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {3, 7} mod 8 to an odd power. - If N is odd, then the sum of exponents of {5} mod 8 prime factors of N is even. - If N ≡ 8 (mod 16), then N has no prime factors congruent to {5} mod 8 to an odd power. k = 18 Primes p of the form a²+18b² : {1, 19} mod 24. if N is a non-negative integer that can be written as a²+18b², then p × N can be written as a²+18b² if N is a non-negative integer that cannot be written as a²+18b², then p × N cannot be written as a²+18b² N can be written as a²+18b² if and only if - N is not congruent to {3, 6} (mod 9). - N has no prime factors congruent to {5, 7, 13, 23} mod 24 to an odd power. - If N is not a multiple of 3, then the sum of exponents of {2, 11, 17} mod 24 prime factors of N is even. k = 22 Primes p of the form a²+22b² : {1, 9, 15, 23, 25, 31, 47, 49, 71, 81} mod 88. if N is a non-negative integer that can be written as a²+22b², then p × N can be written as a²+22b² if N is a non-negative integer that cannot be written as a²+22b², then p × N cannot be written as a²+22b² N can be written as a²+22b² if and only if - N has no prime factors congruent to {3, 5, 7, 17, 27, 37, 39, 41, 45, 53, 57, 59, 63, 65, 67, 69, 73, 75, 79, 87} mod 88 to an odd power. - Sum of exponents of {2, 11, 13, 19, 21, 29, 35, 43, 51, 61, 83, 85} mod 88 prime factors of N is even. k = 25 Primes p of the form a²+25b² : {1, 9} mod 20. if N is a non-negative integer that can be written as a²+25b², then p × N can be written as a²+25b² if N is a non-negative integer that cannot be written as a²+25b², then p × N cannot be written as a²+25b² N can be written as a²+25b² if and only if - N is not congruent to {5, 10, 15, 20} (mod 25). - N has no prime factors congruent to {3, 7, 11, 19} mod 20 to an odd power. - If N is not a multiple of 5, then the sum of exponents of {2, 13, 17} mod 20 prime factors of N is even. k = 28 Edit: At the request of the author, please note that this is incorrect. A corrected version of this is stated below. Primes p of the form a²+28b² : {1, 9, 25} mod 28. if N is a non-negative integer that can be written as a²+28b², then p × N can be written as a²+28b² if N is a non-negative integer that cannot be written as a²+28b², then p × N cannot be written as a²+28b² N can be written as a²+28b² if and only if - N is not congruent to 2 (mod 4). - N has no prime factors congruent to {3, 5, 13, 17, 19, 27} mod 28 to an odd power. - If N is odd, then the sum of exponents of {7, 11, 15, 23} mod 28 prime factors of N is even. - If N ≡ 8 (mod 16), then N has no prime factors congruent to {7, 11, 15, 23} mod 28 to an odd power. k = 37 Primes p of the form a²+37b² : {1, 9, 21, 25, 33, 37, 41, 49, 53, 65, 73, 77, 81, 85, 101, 121, 137, 141, 145} mod 148. if N is a non-negative integer that can be written as a²+37b², then p × N can be written as a²+37b² if N is a non-negative integer that cannot be written as a²+37b², then p × N cannot be written as a²+37b² N can be written as a²+37b² if and only if - N has no prime factors congruent to {3, 5, 7, 11, 13, 17, 27, 29, 45, 47, 57, 61, 63, 67, 69, 71, 75, 83, 89, 93, 95, 97, 99, 105, 107, 109, 113, 115, 117, 123, 125, 127, 129, 133, 139, 147} mod 148 to an odd power. - Sum of exponents of {2, 15, 19, 23, 31, 35, 39, 43, 51, 55, 59, 79, 87, 91, 103, 119, 131, 135, 143} mod 148 prime factors of N is even. k = 58 Primes p of the form a²+58b² : {1, 9, 25, 33, 35, 49, 51, 57, 59, 65, 67, 81, 83, 91, 107, 115, 121, 123, 129, 139, 161, 169, 179, 187, 209, 219, 225, 227} mod 232. if N is a non-negative integer that can be written as a²+58b², then p × N can be written as a²+58b² if N is a non-negative integer that cannot be written as a²+58b², then p × N cannot be written as a²+58b² N can be written as a²+58b² if and only if - N has no prime factors congruent to {3, 5, 7, 11, 13, 17, 19, 23, 27, 41, 43, 45, 53, 63, 71, 73, 75, 89, 93, 97, 99, 103, 105, 109, 111, 113, 117, 125, 131, 137, 141, 147, 149, 151, 153, 155, 163, 165, 167, 171, 173, 175, 177, 181, 183, 185, 193, 195, 197, 199, 201, 207, 211, 217, 223, 231} mod 232 to an odd power. - Sum of exponents of {2, 15, 21, 29, 31, 37, 39, 47, 55, 61, 69, 77, 79, 85, 95, 101, 119, 127, 133, 135, 143, 157, 159, 189, 191, 205, 213, 215, 221, 229} mod 232 prime factors of N is even. Last fiddled with by chalsall on 2013-02-06 at 21:16
 2013-02-04, 03:45 #4 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts Some classical, special cases If $F_k$ is the kth Fibonacci number, then $F_{2n+1}$ = $F_{n}^2$ + $F_{n+1}^2$ So, $F_{2n+1}$ is always the sum of two squares, therefore the square-free part of $F_{2n+1}$ consists entirely of prime factors congruent to {1, 2} mod 4. I'm not sure, if whether $F_{2n+1}$ has got with prime factors congruent to 3 mod 4, if so they must come in pairs. I'm not sure, if whether $F_{2n+1}$ is always being square-free, either. Also, if $L_k$ is the kth Lucas number, then Any prime factor of $L_p$ is congruent to {1, 9} mod 10, where p is a prime. Any number of the form $10^{4n+2}+1$ can be written as a²+5b² form, as follows 101 = 9² + 5 × 2². 1000001 = 999² + 5 × 20². 10000000001 = 99999² + 5 × 200². In general, $10^{4n+2}+1$ = $(10^{2n+1}-1)^2$ + 5 × $(2 \times 10^{n})^2$ As far as I have noticed with, all prime factors of $10^{4n+2}+1$ are always congruent to {1, 9} (mod 20). I'm not sure if whether they can contain prime factors congruent to {3, 7} (mod 20), but that if in case they are being square-free, then the sum of exponents of these {3, 7} (mod 20) prime factors of $10^{4n+2}+1$ will always be even. I'm not sure if whether all the numbers of the form $10^{4n+2}+1$ are always being square-free either. Since $10^{4n+2}+1$ is always being odd, so 2 does not divide with $10^{4n+2}+1$. Since $10^{4n+2}+1$ is always congruent to 1 (mod 10), so 5 does not divide with $10^{4n+2}+1$. Any number of the form $10^{2n+1}+1$ can be written as a²+10b² form, as follows 11 = 1² + 10 × 1². 1001 = 1² + 10 × 10². 100001 = 1² + 10 × 100². 10000001 = 1² + 10 × 1000². 1000000001 = 1² + 10 × 10000². In general, $10^{2n+1}+1$ = $(1)^2$ + 10 × $(10^{n})^2$ As far as I have observed with, all prime factors of $10^{2n+1}+1$ are always congruent to {1, 9, 11, 19} (mod 40). I'm not sure if whether they can contain prime factors congruent to {2, 5, 7, 13, 23, 37} (mod 40), but that if in case they are being square-free, then the sum of exponents of these {2, 5, 7, 13, 23, 37} (mod 40) prime factors of $10^{2n+1}+1$ will always be even. I'm not considering if whether all the numbers of the form $10^{2n+1}+1$ are always being square-free either. Since $10^{2n+1}+1$ is always being odd, so 2 does not divide with $10^{2n+1}+1$. Since $10^{2n+1}+1$ is always congruent to 1 (mod 10), so 5 does not divide with $10^{2n+1}+1$. Any number of the form $2^{2n}+1$ is always being the sum of two squares, as since $2^{2n}+1$ = $(1)^2$ + $(2^{n})^2$ So, the square-free part of $2^{2n}+1$ will always contain prime factors congruent to 1 mod 4. Since $2^{2n}+1$ is always being odd, so 2 does not divide with $2^{2n}+1$. I'm not considering if whether all the numbers of the form $2^{2n}+1$ are always being square-free either. Any number of the form $10^{2n}+1$ is always being the sum of two squares, as since $10^{2n}+1$ = $(1)^2$ + $(10^{n})^2$ So, the square-free part of $10^{2n}+1$ will always contain prime factors congruent to 1 mod 4. Since $10^{2n}+1$ is always being odd, so 2 does not divide with $10^{2n}+1$. I'm not considering if whether all the numbers of the form $10^{2n}+1$ are always being square-free either. Any Fermat Number $2^{2^n}+1$ is always being the sum of two squares, as since $2^{2^n}+1$ = $(1)^2$ + $(2^{2^{n-1}})^2$ Since the Fermat numbers are always being square-free, so, $2^{2^n}+1$ will always contain prime factors congruent to 1 mod 4. Since the Fermat number $2^{2^n}+1$ is always being odd, so 2 does not divide with $2^{2^n}+1$. Any number of the form $2^{2n+1}+1$ can be written as a²+2b² form, as follows 3 = 1² + 2 × 1². 9 = 1² + 2 × 2². 33 = 1² + 2 × 4². 129 = 1² + 2 × 8². 513 = 1² + 2 × 16². 2049 = 1² + 2 × 32². 8193 = 1² + 2 × 64². In general, $2^{2n+1}+1$ = $(1)^2$ + 2 × $(2^{n})^2$ Thereby, the square-free part of $2^{2n+1}+1$ cannot contain with prime factors congruent to {5, 7} (mod 8). As far as I have observed with, all prime factors of $2^{2n+1}+1$ are always congruent to {1, 3} (mod 8). Since $2^{2n+1}+1$ is always being odd, so 2 does not divide with $2^{2n+1}+1$. Since $2^{2n+1}+1$ is always being congruent to {3, 9} (mod 10), so 5 does not divide with $2^{2n+1}+1$. I'm not considering if whether all the numbers of the form $2^{2n+1}+1$ are always being square-free either. Last fiddled with by Raman on 2013-02-04 at 04:20
2013-02-04, 05:18   #5
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

35×41 Posts

Quote:
 Originally Posted by Raman Since the Fermat numbers are always being square-free
Grrr... I may be far behind the news in math... Is this proven? Can you point me to a link?

(Composite Fermat numbers Fn will always contain factors congruent to 1 (mod 2^(n+2)), but from totally different reasons!)

Last fiddled with by LaurV on 2013-02-04 at 05:21

 2013-02-04, 05:30 #6 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts Unique factorization domains Let N be a non-negative integer that can be written as a²+kb² (with a ≥ 0, b ≥ 0). Let p be a prime factor that divides N (raised to an odd power), i.e. pm divides N, pm+1 does not divide N, whereby m is being odd. Then, if p can also always be written as a²+kb² (with a ≥ 0, b ≥ 0), then k = 1, 2, 3. Let N be a non-negative integer that can be written as a²+kb² (with a ≥ 0, b ≥ 0). Let p be a prime factor (p ≠ 2) that divides N (raised to an odd power), i.e. pm divides N, pm+1 does not divide N, whereby m is being odd. Then, if p can also always be written as a²+kb² (with a ≥ 0, b ≥ 0), then k = 1, 2, 3, 4, 7. Class Number One Let N be a non-negative integer that can be written as (a/2)²+k(b/2)² (with a ≥ 0, b ≥ 0). Let p be a prime factor that divides N (raised to an odd power), i.e. pm divides N, pm+1 does not divide N, whereby m is being odd. Then, if p can also always be written as (a/2)²+k(b/2)² (with a ≥ 0, b ≥ 0), then k = 1, 2, 3, 4, 7, 8, 11, 12, 19, 43, 67, 163 For example, 15 = 3 × 5 = 1² + 11 × 2², but neither 3 nor 5 can be written in the form a²+11b². But, if we do consider numbers of the form (a/2)²+11(b/2)², then 3 = (1/2)² + 11 × (1/2)², 5 = (3/2)² + 11 × (1/2)² Class Number Two Let N be a non-negative integer that can be written as a²+kb² (with a ≥ 0, b ≥ 0). Let P be the product of all the prime factors of N which individually can be written in the a²+kb² form. Then, if the sum of exponents of all the prime factors of (N/p) is being even, then besides the values for k = 1, 2, 3 (for which this sum is being always essentially zero), then k = 5, 6, 10, 13, 15, 22, 37, 58 Prime numbers of the form a²+kb² Playing with my own Java code, onto the representation of non-negative integers by using these a²+kb² forms, that I found out with this following thing, stuff. For these following sixty-five values of k, all the prime numbers representable in the a²+kb² form can be given by a set of residue classes (mod 4k), with every prime number of these residue classes being uniquely writable in the a²+kb² form, then k = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, 1848 For example, 21 belongs to this sequence as since the set of primes representable in the form a²+21b² can be given by primes that are being congruent to {1, 25, 37} (mod 84), with every prime number of these residue classes being uniquely writable in the a²+21b² form For example, 24 belongs to this sequence as since the set of primes representable in the form a²+24b² can be given by primes that are being congruent to 1 (mod 24), with every prime number of these residue classes being uniquely writable in the a²+24b² form Prime numbers of the form (a/2)²+k(b/2)² On the other hand, if we loosen the prime numbers of the form a²+kb² onto the prime numbers of the form (a/2)²+k(b/2)², then that I found out For these following values of k, all the prime numbers representable in the (a/2)²+k(b/2)² form can be given by a set of residue classes (mod 4k), with every prime number of these residue classes being uniquely writable in the (a/2)²+k(b/2)² form, then k = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 18, 19, 20, 21, 22, 24, 25, 27, 28, 30, 32, 33, 35, 36, 37, 40, 42, 43, 45, 48, 51, 52, 57, 58, 60, 64, 67, 70, 72, 75, 78, 84, 85, 88, 91, 93, 96, 99, 100, 102, 105, 112, 115, 120, 123, 130, 132, 133, 147, 148, 160, 163, 165, 168, 177, 180, 187, 190, 192, 195, 210, 228, 232, 235, 240, 253, 267, 273, 280, 288, 312, 315, 330, 340, 345, 352, 357, 372, 385, 403, 408, 420, 427, 435, 448, 462, 480, 483, 520, 532, 555, 595, 627, 660, 672, 708, 715, 760, 795, 840, 928, 960, 1012, 1092, 1120, 1155, 1248, 1320, 1365, 1380, 1428, 1435, 1540, 1632, 1848, 1995, 2080, 3003, 3040, 3315, 3360, 5280, 5460, 7392 For example, 11 belongs to this sequence as since the set of primes representable in the form (a/2)²+11(b/2)² can be given by primes that are being congruent to {0, 1, 3, 4, 5, 9} (mod 11), with every prime number of these residue classes being uniquely writable in the (a/2)²+11(b/2)² form For example, 19 belongs to this sequence as since the set of primes representable in the form (a/2)²+19(b/2)² can be given by primes that are being congruent to {0, 1, 4, 5, 6, 7, 9, 11, 16, 17} (mod 19), with every prime number of these residue classes being uniquely writable in the (a/2)²+19(b/2)² form Last fiddled with by Raman on 2013-02-04 at 05:58
 2013-02-04, 14:01 #7 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts do you realize every prime >3 is of form a=2 b=1 for some k ? : 2^2+1(1^2) = 5 2^2+3(1^2) = 7 2^2+7(1^2) = 11 etc. Last fiddled with by science_man_88 on 2013-02-04 at 14:01
 2013-02-04, 14:28 #8 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts Some extra results A prime number p can be written in the form a²+27b² if and only if p ≡ 1 (mod 3), with 2 being a cubic residue (mod p), i.e. p ≡ 1 (mod 3), and then 2(p-1)/3 ≡ 1 (mod p). A prime number p can be written in the form a²+32b² if and only if p ≡ 1 (mod 8), with p-4 being a octic residue (mod p), i.e. p ≡ 1 (mod 8), and then (p-4)(p-1)/8 ≡ 1 (mod p). A prime number p can be written in the form a²+64b² if and only if p ≡ 1 (mod 8), with 2 being a biquadratic residue (mod p), i.e. p ≡ 1 (mod 8), and then 2(p-1)/4 ≡ 1 (mod p). In general In order to write with a prime number p in the form a²+kb², then find out a value of x such that x² ≡ -k (mod p). Then, take the GCD of (x + √-k) and (p) in the ring of integers Z[√-k] = numbers of the form A + B√-k. Then, the GCD of (x + √-k) and (p) will be (a ± b√-k). In order to write with a non-negative integer N in the form a²+kb² - all of whose prime factors can be individually written in the form a²+kb², then, write with each of the individual prime factors of N in the form a²+kb², and then combine them pairwise with, by using with the following formula, by itself (a²+kb²)(c²+kd²) = |ac+kbd|² + k|ad-bc|² (a²+kb²)(c²+kd²) = |ac-kbd|² + k|ad+bc|²
 2013-02-04, 17:56 #9 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 100111010012 Posts Questions 1. If I understand correctly, then SOME, but not ALL of the primes of the following residue classes {0, 1, 3, 4, 5, 9} mod 11 can be written in the form a²+11b² but the primes of the other residue classes (mod 11) are the only primes that cannot be present as prime factors raised to an odd power, for the numbers that can be written in the form a²+11b². Similarly, that SOME, but not ALL of the primes of the following residue classes {0, 1, 4, 5, 6, 7, 9, 11, 16, 17} mod 19 can be written in the form a²+19b² but the primes of the other residue classes (mod 19) are the only primes that cannot exist as prime factors raised to an odd power, for the numbers that can be written in the form a²+19b². SOME, but not ALL of the primes of the following residue classes {1, 9, 15, 23, 25, 39} mod 56 can be written in the form a²+14b². SOME, but not ALL of the primes of the following residue classes {1, 9, 13, 17, 21, 25, 33, 49, 53} mod 68 can be written in the form a²+17b². So, is it being possible to give explicitly (in the closed form), which of the primes from within these residue classes (mod 4k), can be written in the forms a²+11b², a²+14b², a²+17b², a²+19b²? 2. A prime number p can be written in the form a²+21b² if and only if p is congruent to {1, 25, 37} mod 84. Similarly, that a prime number p can be written in the form a²+24b² if and only if p is congruent to {1} mod 24. Does anyone have a simple closed form, or atleast with a polynomial time efficient algorithm (polynomial in the number of digits of N) for what non-negative integers N, in general, can be written in the forms a²+21b², a²+24b², etc.? 3. Given a fixed value of k, my own JAVA program designates all the available primes into three different categories {ALL, SOME, NONE} as follows A prime p is of type ALL if it can be written in the form a²+kb². i.e. if p × N can be written in the form a²+kb², then N can be written in the form a²+kb². if p × N cannot be written in the form a²+kb², then N cannot be written in the form a²+kb². A prime p is of type SOME if there exist some numbers N that can be written in the form a²+kb², which contains the prime factor of p being raised to an odd power, but p cannot quite directly be written in the form a²+kb². A prime p is of type NONE if there does not exist any numbers N that can be written in the form a²+kb², which contains the prime factor of p being raised to an odd power. If we consider all the primes of a certain residue class (mod 4k), then, For k ≤ 3, any residue class (mod 4k) contains with a single type of following prime. - either ALL or NONE (We consider with the residue classes for which there is being at least one prime) k = 4 is being the lowest value of k, for which there exist residue classes (mod 4k), that contains with the following type of prime: SOME. For k ≤ 10, any residue class (mod 4k) contains with a single type of prime. (We consider with the residue classes for which there is being at least one prime) k = 11 is being the lowest value of k, for which there exist residue classes (mod 4k), that contains with two different types of primes: ALL / SOME. What is the lowest value of k, for which there exist residue classes (mod 4k), that contains with two different types of primes: SOME / NONE? Answer: k = 96 Is it possible that there exist a value of k, for which there exist residue classes (mod 4k), that contains with two different types of primes: ALL / NONE? Or even containing with all the three different types of primes: ALL / SOME / NONE? Answer: k = 107 4. Thereby, is it always being true that, if in case that, a prime number p can be written in the form a²+kb², → then p × N can be written in the form a²+kb², if and only if N can be written in the form a²+kb²? → then p × N cannot be written in the form a²+kb², if and only if N cannot be written in the form a²+kb²? Yes, I think so!
 2013-02-06, 12:45 #10 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts This was pretty complicated to be generated. But once verified, then, they have been very much interesting, beautiful and classical! The following are the square-free values of k such that their discriminants values of 4k have got with a class number of 4, inside the imaginary quadratic field Z[√-k], by itself. You can check by yourself that I got all of them to be right, correctly! It helps me to understand how the factorization of ideals work out inside a number field, by itself! Class Number 1 (Unique factorization domains?): k = 1, 2, 3, 4, 7 Class Number 2: k = 5, 6, 8, 9, 10, 12, 13, 15, 16, 18, 22, 25, 28, 37, 58 Class Number 4: k = 21, 24, 30, 33, 40, 42, 45, 48, 57, 60, 70, 72, 78, 85, 88, 93, 102, 112, 130, 133, 177, 190, 232, 253 Class Number 8: k = 105, 120, 165, 168, 210, 240, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760 Class Number 16: k = 840, 1320, 1365, 1848 k = 21 Primes p of the form a²+21b²: All primes congruent to [1, 25, 37] mod 84. if N is a non-negative integer that can be written as a²+21b², then p × N can be written as a²+21b² if N is a non-negative integer that cannot be written as a²+21b², then p × N cannot be written as a²+21b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 11, 23, 71] mod 84 Class B primes: All primes congruent to [3, 7, 19, 31, 55] mod 84 Class C primes: All primes congruent to [5, 17, 41] mod 84 N can be written as a²+21b² if and only if - N has no prime factors congruent to [13, 29, 43, 47, 53, 59, 61, 65, 67, 73, 79, 83] mod 84 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 30 Primes p of the form a²+30b²: All primes congruent to [1, 31, 49, 79] mod 120. if N is a non-negative integer that can be written as a²+30b², then p × N can be written as a²+30b² if N is a non-negative integer that cannot be written as a²+30b², then p × N cannot be written as a²+30b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 17, 23, 47, 113] mod 120 Class B primes: All primes congruent to [3, 13, 37, 43, 67] mod 120 Class C primes: All primes congruent to [5, 11, 29, 59, 101] mod 120 N can be written as a²+30b² if and only if - N has no prime factors congruent to [7, 19, 41, 53, 61, 71, 73, 77, 83, 89, 91, 97, 103, 107, 109, 119] mod 120 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 33 Primes p of the form a²+33b²: All primes congruent to [1, 25, 37, 49, 97] mod 132. if N is a non-negative integer that can be written as a²+33b², then p × N can be written as a²+33b² if N is a non-negative integer that cannot be written as a²+33b², then p × N cannot be written as a²+33b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 17, 29, 41, 65, 101] mod 132 Class B primes: All primes congruent to [3, 11, 23, 47, 59, 71, 119] mod 132 Class C primes: All primes congruent to [7, 19, 43, 79, 127] mod 132 N can be written as a²+33b² if and only if - N has no prime factors congruent to [5, 13, 31, 35, 53, 61, 67, 73, 83, 85, 89, 91, 95, 103, 107, 109, 113, 115, 125, 131] mod 132 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 42 Primes p of the form a²+42b²: All primes congruent to [1, 25, 43, 67, 121, 163] mod 168. if N is a non-negative integer that can be written as a²+42b², then p × N can be written as a²+42b² if N is a non-negative integer that cannot be written as a²+42b², then p × N cannot be written as a²+42b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 23, 29, 53, 71, 95, 149] mod 168 Class B primes: All primes congruent to [3, 17, 41, 59, 83, 89, 131] mod 168 Class C primes: All primes congruent to [7, 13, 31, 55, 61, 103, 157] mod 168 N can be written as a²+42b² if and only if - N has no prime factors congruent to [5, 11, 19, 37, 47, 65, 73, 79, 85, 97, 101, 107, 109, 113, 115, 125, 127, 137, 139, 143, 145, 151, 155, 167] mod 168 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 57 Primes p of the form a²+57b²: All primes congruent to [1, 25, 49, 61, 73, 85, 121, 157, 169] mod 228. if N is a non-negative integer that can be written as a²+57b², then p × N can be written as a²+57b² if N is a non-negative integer that cannot be written as a²+57b², then p × N cannot be written as a²+57b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 29, 41, 53, 65, 89, 113, 173, 185, 221] mod 228 Class B primes: All primes congruent to [3, 19, 31, 67, 79, 91, 103, 127, 151, 211, 223] mod 228 Class C primes: All primes congruent to [11, 23, 35, 47, 83, 119, 131, 191, 215] mod 228 N can be written as a²+57b² if and only if - N has no prime factors congruent to [5, 7, 13, 17, 37, 43, 55, 59, 71, 77, 97, 101, 107, 109, 115, 125, 137, 139, 143, 145, 149, 155, 161, 163, 167, 175, 179, 181, 187, 193, 197, 199, 203, 205, 217, 227] mod 228 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 70 Primes p of the form a²+70b²: All primes congruent to [1, 9, 39, 71, 79, 81, 121, 151, 169, 191, 239, 249] mod 280. if N is a non-negative integer that can be written as a²+70b², then p × N can be written as a²+70b² if N is a non-negative integer that cannot be written as a²+70b², then p × N cannot be written as a²+70b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 37, 43, 53, 67, 93, 107, 123, 163, 197, 253, 267, 277] mod 280 Class B primes: All primes congruent to [5, 19, 59, 61, 69, 101, 131, 139, 171, 181, 229, 251, 269] mod 280 Class C primes: All primes congruent to [7, 17, 33, 47, 73, 87, 97, 103, 143, 153, 167, 223, 257] mod 280 N can be written as a²+70b² if and only if - N has no prime factors congruent to [3, 11, 13, 23, 27, 29, 31, 41, 51, 57, 83, 89, 99, 109, 111, 113, 117, 127, 129, 137, 141, 149, 157, 159, 173, 177, 179, 183, 187, 193, 199, 201, 207, 209, 211, 213, 219, 221, 227, 233, 237, 241, 243, 247, 261, 263, 271, 279] mod 280 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 78 Primes p of the form a²+78b²: All primes congruent to [1, 25, 49, 55, 79, 103, 121, 127, 199, 217, 289, 295] mod 312. if N is a non-negative integer that can be written as a²+78b², then p × N can be written as a²+78b² if N is a non-negative integer that cannot be written as a²+78b², then p × N cannot be written as a²+78b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 41, 47, 71, 89, 119, 137, 161, 167, 215, 239, 281, 305] mod 312 Class B primes: All primes congruent to [3, 29, 35, 53, 77, 101, 107, 131, 155, 173, 179, 251, 269] mod 312 Class C primes: All primes congruent to [13, 19, 37, 67, 85, 109, 115, 163, 187, 229, 253, 301, 307] mod 312 N can be written as a²+78b² if and only if - N has no prime factors congruent to [5, 7, 11, 17, 23, 31, 43, 59, 61, 73, 83, 95, 97, 113, 125, 133, 139, 145, 149, 151, 157, 175, 181, 185, 191, 193, 197, 203, 205, 209, 211, 223, 227, 233, 235, 241, 245, 257, 259, 263, 265, 271, 275, 277, 283, 287, 293, 311] mod 312 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. Last fiddled with by Raman on 2013-02-06 at 12:58
 2013-02-06, 12:47 #11 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 4E916 Posts k = 85 Primes p of the form a²+85b²: All primes congruent to [1, 9, 21, 49, 69, 81, 89, 101, 121, 149, 161, 169, 189, 229, 281, 321] mod 340. if N is a non-negative integer that can be written as a²+85b², then p × N can be written as a²+85b² if N is a non-negative integer that cannot be written as a²+85b², then p × N cannot be written as a²+85b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 43, 47, 67, 83, 87, 103, 123, 127, 183, 203, 223, 247, 263, 287, 307, 327] mod 340 Class B primes: All primes congruent to [5, 17, 37, 57, 73, 97, 113, 133, 173, 177, 193, 197, 233, 277, 313, 317, 333, 337] mod 340 Class C primes: All primes congruent to [11, 31, 39, 71, 79, 91, 99, 131, 139, 159, 199, 211, 231, 279, 299, 311] mod 340 N can be written as a²+85b² if and only if - N has no prime factors congruent to [3, 7, 13, 19, 23, 27, 29, 33, 41, 53, 59, 61, 63, 77, 93, 107, 109, 111, 117, 129, 137, 141, 143, 147, 151, 157, 163, 167, 171, 179, 181, 191, 201, 207, 209, 213, 217, 219, 227, 237, 239, 241, 243, 249, 251, 253, 257, 259, 261, 267, 269, 271, 273, 283, 291, 293, 297, 301, 303, 309, 319, 329, 331, 339] mod 340 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 93 Primes p of the form a²+93b²: All primes congruent to [1, 25, 49, 97, 109, 121, 133, 157, 169, 193, 205, 253, 289, 349, 361] mod 372. if N is a non-negative integer that can be written as a²+93b², then p × N can be written as a²+93b² if N is a non-negative integer that cannot be written as a²+93b², then p × N cannot be written as a²+93b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 35, 47, 59, 71, 95, 107, 131, 143, 191, 227, 287, 299, 311, 335, 359] mod 372 Class B primes: All primes congruent to [3, 31, 43, 55, 79, 91, 115, 127, 139, 151, 199, 223, 247, 259, 271, 331, 367] mod 372 Class C primes: All primes congruent to [17, 29, 53, 65, 77, 89, 137, 161, 185, 197, 209, 269, 305, 353, 365] mod 372 N can be written as a²+93b² if and only if - N has no prime factors congruent to [5, 7, 11, 13, 19, 23, 37, 41, 61, 67, 73, 83, 85, 101, 103, 113, 119, 125, 145, 149, 163, 167, 173, 175, 179, 181, 187, 203, 211, 215, 221, 229, 233, 235, 239, 241, 245, 251, 257, 263, 265, 275, 277, 281, 283, 293, 295, 301, 307, 313, 317, 319, 323, 325, 329, 337, 343, 347, 355, 371] mod 372 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 102 Primes p of the form a²+102b²: All primes congruent to [1, 25, 49, 55, 103, 121, 127, 145, 151, 169, 217, 223, 247, 271, 319, 361] mod 408. if N is a non-negative integer that can be written as a²+102b², then p × N can be written as a²+102b² if N is a non-negative integer that cannot be written as a²+102b², then p × N cannot be written as a²+102b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 35, 53, 59, 77, 83, 101, 149, 155, 179, 203, 251, 293, 341, 365, 389, 395] mod 408 Class B primes: All primes congruent to [3, 37, 61, 91, 109, 133, 139, 163, 181, 211, 235, 277, 283, 301, 379, 397, 403] mod 408 Class C primes: All primes congruent to [17, 23, 41, 65, 71, 95, 113, 143, 167, 209, 215, 233, 311, 329, 335, 377, 401] mod 408 N can be written as a²+102b² if and only if - N has no prime factors congruent to [5, 7, 11, 13, 19, 29, 31, 43, 47, 67, 73, 79, 89, 97, 107, 115, 125, 131, 137, 157, 161, 173, 175, 185, 191, 193, 197, 199, 205, 227, 229, 239, 241, 245, 253, 257, 259, 263, 265, 269, 275, 281, 287, 295, 299, 305, 307, 313, 317, 325, 331, 337, 343, 347, 349, 353, 355, 359, 367, 371, 373, 383, 385, 407] mod 408 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 130 Primes p of the form a²+130b²: All primes congruent to [1, 9, 49, 51, 81, 121, 129, 131, 139, 179, 209, 211, 251, 259, 289, 321, 329, 339, 361, 419, 441, 451, 459, 491] mod 520. if N is a non-negative integer that can be written as a²+130b², then p × N can be written as a²+130b² if N is a non-negative integer that cannot be written as a²+130b², then p × N cannot be written as a²+130b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 33, 57, 67, 73, 83, 97, 123, 137, 163, 177, 187, 193, 203, 227, 267, 297, 307, 323, 353, 427, 457, 473, 483, 513] mod 520 Class B primes: All primes congruent to [5, 21, 31, 71, 109, 111, 119, 141, 149, 151, 189, 229, 239, 271, 279, 301, 319, 349, 359, 421, 431, 461, 479, 501, 509] mod 520 Class C primes: All primes congruent to [13, 23, 53, 77, 87, 103, 127, 133, 157, 173, 183, 207, 237, 263, 277, 287, 303, 367, 373, 407, 413, 477, 493, 503, 517] mod 520 N can be written as a²+130b² if and only if - N has no prime factors congruent to [3, 7, 11, 17, 19, 27, 29, 37, 41, 43, 47, 59, 61, 63, 69, 79, 89, 93, 99, 101, 107, 113, 147, 153, 159, 161, 167, 171, 181, 191, 197, 199, 201, 213, 217, 219, 223, 231, 233, 241, 243, 249, 253, 257, 261, 269, 281, 283, 291, 293, 309, 311, 313, 317, 327, 331, 333, 337, 341, 343, 347, 357, 363, 369, 371, 379, 381, 383, 387, 389, 391, 393, 397, 399, 401, 409, 411, 417, 423, 433, 437, 439, 443, 447, 449, 453, 463, 467, 469, 471, 487, 489, 497, 499, 511, 519] mod 520 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. k = 133 Primes p of the form a²+133b²: All primes congruent to [1, 9, 25, 81, 85, 93, 121, 137, 149, 169, 177, 197, 225, 233, 253, 277, 289, 305, 309, 365, 389, 429, 457, 473, 501, 505, 529] mod 532. if N is a non-negative integer that can be written as a²+133b², then p × N can be written as a²+133b² if N is a non-negative integer that cannot be written as a²+133b², then p × N cannot be written as a²+133b² Let us define Class A, Class B, Class C primes as follows: Class A primes: All primes congruent to [2, 15, 51, 67, 71, 79, 107, 127, 135, 151, 155, 179, 183, 211, 219, 295, 303, 319, 331, 375, 379, 407, 431, 459, 471, 487, 515, 527] mod 532 Class B primes: All primes congruent to [7, 19, 47, 55, 83, 87, 111, 115, 131, 139, 159, 187, 195, 199, 215, 251, 271, 283, 311, 327, 339, 367, 391, 419, 423, 467, 479, 495, 503] mod 532 Class C primes: All primes congruent to [13, 33, 41, 69, 89, 97, 117, 129, 145, 173, 181, 185, 241, 257, 265, 269, 293, 297, 325, 341, 369, 409, 433, 489, 493, 509, 521] mod 532 N can be written as a²+133b² if and only if - N has no prime factors congruent to [3, 5, 11, 17, 23, 27, 29, 31, 37, 39, 43, 45, 53, 59, 61, 65, 73, 75, 99, 101, 103, 109, 113, 123, 125, 141, 143, 153, 157, 163, 165, 167, 191, 193, 201, 205, 207, 213, 221, 223, 227, 229, 235, 237, 239, 243, 249, 255, 261, 263, 267, 275, 279, 281, 291, 299, 307, 313, 317, 321, 333, 335, 337, 345, 347, 349, 351, 353, 355, 359, 363, 373, 377, 381, 383, 387, 393, 395, 397, 401, 403, 405, 411, 415, 417, 421, 425, 435, 439, 443, 445, 447, 449, 451, 453, 461, 463, 465, 477, 481, 485, 491, 499, 507, 517, 519, 523, 531] mod 532 to an odd power. - Sum of exponents of Class A prime factors of N, sum of exponents of Class B prime factors of N, sum of exponents of Class C prime factors of N are all even, or are all odd. Last fiddled with by Raman on 2013-02-06 at 12:59

 Similar Threads Thread Thread Starter Forum Replies Last Post MooMoo2 Other Chess Games 5 2016-10-22 01:55 jasong jasong 10 2015-12-14 06:38 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 02:12.

Fri May 27 02:12:01 UTC 2022 up 43 days, 13 mins, 0 users, load averages: 1.34, 1.37, 1.38