Primes Definition and 291 Threads

I am trying to understand Euclid's proof of infinite primes. So let's say we have a finite list of primes n1, n2 ... N where N is the largest prime . Then we take the product of all of these prime numbers, and we will call it Q . Then we add 1 to it . so this number is either prime or...

It is true that phi(pq)=(p-1)(q-1) when p and q are distinct primes, but is it true that given phi(pq) = (p-1)(q-1) then p and q have to be distinct primes? It seems intuitive, but I'm having some difficulty proving it. Also, if this was true, is it possible to generalize this into more than 2...

From what I had read, Euler had originally proved the infinitude of primes through proving his product formula and equating the primorial to the divergent harmonic series. \sum^{\infty}_{n=1}\frac{1}{n^{s}} = \prod^{\infty}_{p}\frac{1}{1-p^{-s}} where p ranges through the primes. However, the...

Primes between 1 and a limit! I just discovered something cool! I found out a method to find a close approximate to the number of primes between 1 a certain limit. If n is the limit, then number of primes is approximately equal to n/(natural log of n). For example, number of primes between 1...

I had an idea a while back and did an experiment concerning primes. It began with the idea that the distribution of prime numbers must be somehow determinable. So I used photoshop and created a white line several pixels wide and several million pixels long, each pixel along the length...

great article http://plus.maths.org/content/music-primes

Homework Statement Hi. I need to prove (or at least make a conjecture) about the infinitude of primes in these cases. 1) N^2+2 2) N^2-2 3) N^2+2N+2 4) N^2+3N+2 Homework Equations none? The Attempt at a Solution Already solved for number 4. This is always even, therefore there is not an...

Homework Statement The idea of this problem is to investigate the solutions to x^2=1 (mod pq), where p,q are distinct odd primes. (a) Show that if p is an odd prime, then there are exactly two solutions (mod p) to x^2=1 (mod p). (Hint: difference of two squares) (b) Find all pairs...

Homework Statement Let b1 through b_phi(m) be integers between 1 and m that are coprime to m. Let B be the product of these integers. Show that B must be congruent to 1 or -1 (mod m) Homework Equations None. The Attempt at a Solution Well, I know that the quantity B appears during the...

Let p,q be two different primes from 5 onwards (not 2 or 3). Let p be the biggest of the two. The difference of squares p^2 - q^2, since p,q are both odd, is always a multiple of 8 (easy to prove). So take the integer k = (p^2 - q^2) / 8. It turns out that k seems to be (says friend computer)...

Homework Statement I have to prove or disprove the following: Part a) If p is prime and p | (a2 + b2) and p | (c2 + d2), then p | (a2 - c2) Part b) f p is prime and p | (a2 + b2) and p | (c2 + d2), then p | (a2 + c2) Homework Equations The Attempt at a Solution Part a)...

Instead of using a sieve to remove non-primes from the sequence. 6x-1 x =0 to x=n 6x+1 x=0 to x= n What if you calculate and remove the non-primes. I have determined how to calculate the non-primes in this set. By subtracting them from the entire set you are left with all primes. I find this...

Prove that sum of two primes can never be twice a prime p.s: find the actual edited q in 4th post belowsorry for the mistake

Prove, that if (m,n) = 1 // m and n are two different primes then (2m -1, 2mn -1/2m -1) = 1

Homework Statement 1. Let G and H be finite groups and let a: G → H be a group homomorphism. Show that if |G| is a prime, then a is either one-to-one or the trivial homomorphism. 2. Let G and H be finite groups and let a : G → H be a group homomorphism. Show that if |H| is a prime, then a...

Hi All, So I was just wondering if there is a formula for the number of ways a number can be written as a sum of squares?(Without including negatives, zero or repeats). For example 5=2^2+1^2. (There is only one way for 5). Second question along this line is: In how many ways can a number...

Hello PhysicsForums people! Could someone show me how there are inifintely many primes in Q[Sqrt(d)]? I figure this will be very similar to the proof of there being infinitely many primes in Z. I cited the above from Wikipedia -Prime Number - The Number of Prime Numbers

I have been trying to write a program whose function is to find all of the prime numbers between 0 and n using the "Sieve of Eratosthenes" method. (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) using bit manipulation and bit arrays and the print out the number of primes found, the first...

The Chinese remainder theorem tells us that the system of equations: \begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align} Uniquely determines all numbers in the range: X<N=n_1n_2\ldots n_k and that all solutions are...

Homework Statement If p is prime \sqrt{p} is prime. Are there flaws in my proof ? Homework Equations The Attempt at a Solution Assume \sqrt{p}=\frac{m}{n} and gcd(m,n)=1 p = \frac{m^{2}}{n^{2}} Since p is an integer n^{2}|m^{2} but gcd(m,n)=1 Therefore...

Was thinking a bit about linear combination of primes and my conclusions are bellow. I presume their is some theorem to capture this but I don't know it's name. If p1 p2 are primes and n1 or n2 are positive integers, then there should be unique a minimum n1 n2 pair such that: x=p_1n_1+p_2n_2...

is the following asymptotic approximation valid whenever dealing sums over primes ?? \sum_{p\le x}f(p) \sim \int_{2}^{x}\frac{f(x)dx}{log(x)}

Twin primes may occur in pairs - i.e. 11, 13, 17, 19. A cursory check seems to indicate that they have to be of the form 90k + 11, 13, 17, 19. Has this ever been proven? If so has it ever been proven that the set of k's is infinite or is it finite?

"11 and 101 are primes, whereas 1001 is not (7*11*13). Find the next smallest prime of the form 100...01, and show that it is the next" I'm fairly sure that there no primes of the form 10^k + 1 above 101, but I can't seem to find a complete proof. Consider the general case of factorising...

Subsets of the set of primes -- uncountable or countable?? Cantor proved that the sub-sets of the natural numbers are uncountable. assuming that the the set of primes can be put in a 1-to-1 matching with the natural numbers (which I believe they can...) then it would follow that the sub...

hey guys, I am a student engineer and have found that the laws we use are primarily based off of stats. this has led me to an interest in number theory and groupings. I was hoping someone could help me with somehing, i would like to know the relevance of the first 3 primes(2,3,5) to math in...

I came across this: Show that if p denotes an odd prime, then 2^((p-1)/2) = +1 (mod p). So basically, this is asking me to show that p|2^((p-1)/2)-1 AND p|2^((p-1)/2)+1 But I'm stuck from there. What am I missing? Could someone help me with the proof?

Howdy, all. I am not sure if this is the right forum for this question. It isn't exactly an homework question, but it does stem very closely from a homework assignment in a first year graduate course in Abstract Algebra. The assignment has come and gone with limited success on my part, but...

Homework Statement I am proving something different and need this to be true. choose prime p > 11. then p^2 is less than the product of all primes that came before it. Homework Equations U(n)= {1, a_1, ... a_k} this is the ring of numbers co prime to n. ex: let p=13. 13^2 =...

I am aiming to prove the following: Let 2 = p1 < p2 < p3... be the sequence of primes in increasing order. Prove that pn ≤ 22n-1.(Hint: Show that the method used to prove Euclid’s Theorem also proves that pn ≤ p1p2...pn−1 + 1.) So I started doing the proof via induction, letting n=2 be my...

This isn't a homework problem, but something I was kicking around. Thus far it has worked for the first 20 primes I could calculate in my head. Does anyone know why this shouldn't work, or an example of it not working for the a specific prime number? The idea is that all prime numbers can be...

There was a part c and d from a question I couldn't answer. Let R = \{ a/b : a, b \in \mathbb{Z}, b \equiv 1 (\mod 2) \}. a) was find the units, b) was show that R\setminus U(R) is a maximal ideal. Both I was successful. But c) is find all primes, which I believe i only found one...the...

Euclid's proof: 1) Assume there is a finite number of primes. 2) Let Pn be the largest prime. 3) Let X be the P1 * P2 ... * Pn + 1 At this point the statement is that "X cannot be divided by P1 through Pn", but why is that? This is not self-obvious to me. How can I know this? k

Here is an interesting problem that I've been thinking about for a while: Let p be a prime s.t. p = 4m+1 for some integer m. Show that p divides n^2 + 1, where n = (2m)! It comes from a section on principal ideal domains and unique factorization domains. It is well-known that p is the...

Homework Statement I have been trying to come up with a program to calculate twin primes using a sieve algorithm in Fortran. So far I have been successful in creating one that finds primes, but I am having difficulty finding one that finds prime twins. If I knew how to do this I could find...

http://mathworld.wolfram.com/news/2009-06-07/mersenne-47/ When a new large number such as this is discovered, does anything interesting usually follow from it or does everyone say "Yes... there it is, now let's find the next one."?

Find all odd primes p, if any, so that p divides \sum_{n=1}^{103} n^{p-1}

Homework Statement First of all, hi everyone! I'm quite new in number theory, and need help on this one badly... Determine all prime numbers p so p2 divides 5p2+1. Homework Equations Euler's theorem: If a and m are coprimes then...

Hi all, so I was looking at Legendre symbols, and I saw that \left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}. How does one show that \frac{p^2-1}{8} is always an integer? That is, how can we show that 8 | p^2-1? Can a similar method be applied to show that 24 | p^3-p? Thanks :-)...

Homework Statement Show that the only three consecutive numbers that are primes are 3,5,7. Homework Equations The Attempt at a Solution let p, p+2, p+4 be three consecutive odd numbers If p=0(mod3), p is divisible by 3 If p=1(mod 3), p+2 is divisible by 3 If p=2(mod3), p+4 is...

After reading 1 of the posts in this forum , I had a look at the millenium problems . There I saw the problem of proving if N=NP . I really did not understand what is NP and what is P ( I checked the Wikipedia link but this got me even more confused ... It talked of a non deterministic...

for all fermat no.s, fi-1=[fi-1-1]2 all fermat no.s are of form 6Ni+5 Ni+1=6Ni2+8Ni+2 a no. of form 6N+5 is composite only when N is of form 6n1n2+5n1+n2 if we could assume that all fermat no.s after f4 are not prime, that means all Nis are of form 6n1n2+5n1+n2, i>4 that means that either...

the idea is is there a Linear operator L so L | \phi _n > =p_n |\phi_n > with p_n being the nth prime and L a linear operator , is it possible to have an spectral interpretation for prime numbers ?

"Of the numbers N>1, only 4 and 6 cannot be expressed as a sum of prime numbers with unique values."

Near the end of Euclid's proof he says that if you multiply all our known primes from 2 to Pn and then add 1 to it, the number isn't divisible by any of our primes up to Pn, because it leaves the remainder 1. Why is that? How does he know that it will always leave the remainder 1? Couldn't...

where could i get some info about the function \sum_{p} p^{-s}=P(s) * the functional equation relating P(s) and P(1-s) * the relation with Riemann zeta

Is the density of primes considerably greater nearer the geometric average of two consecutive square numbers? [Think of deconstructing a square of integral area n2 into composite rectangles of diverging (n-1)(n+1), (n-2)(n+2), (n-3)(n+3)... .] This reasoning may work to a lesser yet...

i saw this conjecture on the web but do not know if is true the number of primes between the expressions x^2 and (x+1)^2 for every x or at least for x bigger than 100 is equal to the Number of primes less than 2x+1 (the x are the same)

The largest known primes for some time have all been Mersenne primes. Can it be shown either that there may exist or cannot exist unknown primes less than the largest known prime?

Can someone please tell me how to go about answering a question like this? I've been racking my brain for a long time and still don't have a clue...I guess because my background in algebra/number theory really isn't that strong. "What is the greatest integer that divides p^4 - 1 for every...