20160907, 17:43  #12 
Aug 2006
5987_{10} Posts 

20160907, 20:12  #13 
Dec 2012
The Netherlands
2^{3}·3^{2}·5^{2} Posts 
We can do something similar with polynomials.
Let p be a prime number, and take any nonzero polynomial f with coefficients from the integers modulo p. Then f has the form \[f=a_0+a_1x+a_2x^2+a_3x^3+\ldots +a_mx^m\] where m can be chosen so that \(a_m\neq 0\). We call m the degree of f. If the degree of f is 0 then we simply have \(f=a_0\) and call f a constant polynomial. We call the nonzero constant polynomials units  they play the same role as 1 (and 1) in the integers because they divide everything. If \(a_m=1\), we say the polynomial is monic. Any nonzero polynomial can be turned into a monic polynomial by dividing by a unit, so in practice we can work with monic polynomials (just as we usually prefer positive integers in Number Theory). We call f irreducible if it is not a unit and cannot be written as the product of two polynomials unless one of them is a unit. The monic irreducible polynomials here play the role of the prime numbers in Number Theory. Now let n be an integer with n≥1. If we multiply together all the monic irreducible polynomials whose degree divides n, it can be shown that we get the polynomial \(x^{p^n}x\). In particular, any monic irreducible polynomial with coefficients in the integers modulo p and whose degree divides n (except the polynomial x itself) is a factor of \(x^{p^n1}1\). 
20160907, 22:48  #14  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,333 Posts 
Quote:
Quote:
105 divides all the positive odd primes less than 8 and it is not of the form 2^n1 but it is of the form/equal to 2^713. I think perhaps you are the one who misunderstood him. Last fiddled with by a1call on 20160907 at 22:50 

20160908, 01:14  #15 
Aug 2006
5,987 Posts 

20160908, 01:30  #16 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,333 Posts 
May be I just don't have the gray matter to understand what is being said. I was out and about all day and posting via smart phone. Did not have a chance to look up the sequence:
https://oeis.org/A123239 So is he saying that: * "Primes that do not divide 2^n1 for any n" constitute the set of all odd prime numbers? That doesn't seem right. How about 232^111 to keep the exponent a prime for a better likelihood. * What is exactly different between 2^n1 & 3^n2 * There are primes that can divide 3^n2 (5) and there are primes that can't (2). * There are primes that can divide 2^n1 (23) and ..... * Are there no odd primes that do not divide 2^n1 for at least one n? is that what being said here? Last fiddled with by a1call on 20160908 at 01:39 
20160908, 01:50  #17  
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20160908 at 01:56 

20160908, 02:09  #18 
"Rashid Naimi"
Oct 2015
Remote to Here/There
91D_{16} Posts 
I can see that 2^n1 can be divisible by any odd prime number. What I have trouble figuring out is how 3^n2 can not be divided by 3 for any integer n.
Thinking out loud: 3^n2=3m 3^n=3m+2 (that makes sense and would make sense for any non zero integer, indivisible by 3 instead of 2 such as 3^n1) obviously 3^n3k can and will always be divisible by 3 3^n2=11m 3^n=11m+2 This is more difficult for me to see 11m+2 can certainly be divisible by 3. Why it can't be a power of 3, no clue. Last fiddled with by a1call on 20160908 at 02:16 
20160908, 02:09  #19 
Aug 2006
5,987 Posts 
For every prime p > 2, there is some integer n such that p  (2^n  1). But the same is not true for 3^n  2: there are infinitely many primes p such that p does not divide 3^n  2 for any integer n. devarajkandadai claimed that the first case was unique [among exponentials] and the second was generic, but that is not correct: there are others like, say, 4^n  64 which should have the same property (here we can insist that n > 3 to avoid triviality).

20160908, 02:23  #20  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
based on this we can already conclude that if n>11 that at least one n<=11 shares a congruence class with it so we only need to check up to n=11. now let's check the first 11 n values mod 11: 3^1=3 mod 11 3^2=9 mod 11 3^3=5 mod 11 3^4=4 mod 11 3^5=1 mod 11 3^6=3 mod 11 < looping value already we can stop ( due to a modular property). there is no 2 mod 11 value in our loop therefore using the fact it will loop we can conclude that no n value produces 2 mod 11. 

20160908, 02:35  #21  
"Rashid Naimi"
Oct 2015
Remote to Here/There
4435_{8} Posts 
Quote:
Thank you, Science man. 

20160908, 03:33  #22 
Aug 2006
1011101100011_{2} Posts 
Yes, well done sm88.
My example of 4^n  64 was constructed to take advantage of this property in a way that guarantees that I get the divisibility promised: since it's 0 at n = 3 , any prime not dividing 4 will loop back through that modular 0. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
method to find primes (in a certain form)  Alberico Lepore  Alberico Lepore  10  20180131 19:26 
Fast modular reduction for primes < 512 bits?  BenR  Computer Science & Computational Number Theory  2  20160327 00:37 
Fast Mersenne Testing on the GPU using CUDA  Andrew Thall  GPU Computing  109  20140728 22:14 
DC chance to find Mersenne Prime  houding  PrimeNet  1  20140224 20:25 
Fast calculations modulo small mersenne primes like M61  Dresdenboy  Programming  10  20040229 17:27 