My Math Forum Primes and Factoring

 Number Theory Number Theory Math Forum

April 20th, 2018, 05:55 AM   #21
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by penrose Does that proof look okay?
Yep, that's fine.

 April 29th, 2018, 07:36 AM #22 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 For clarification, if p is a prime then 1, 2, . . . . . . p-1 is a multiplicative group mod p. The 2-cycle of numbers generated by 2 of form $2^n$ mod p is a subgroup (not necessarily proper). The size of the subgroup must divide p-1. For example, 1, 2, . . . . 6 is the multiplicative group mod 7 and the 2-cycle 2, 4, 1 is a subgroup. The subgroup has size 3 which divides 6. Let's designate the length of the 2-cycle for n by $[n]_2$ Then $[7]_2 = 3$. If we look at the prime number 11, $[11]_2 = 10$. Thm: If n > 1 is an odd number and [n]_2 = n-1, then n is a prime number. Proof: ???
April 30th, 2018, 03:05 AM   #23
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by penrose Thm: If $n > 1$ is an odd number and $[n]_2 = n-1$, then $n$ is a prime number. Proof: ???
This is just a triviality: the multiplicative group of integers modulo $n$ has size less than or equal to $n-1$, with equality if and only if $n$ is prime. So it could only have a subgroup of order $n-1$ if $n$ is prime.

There's nothing special about $2$ here. If there is any integer $k$ such that $[n]_k = n-1$, then $n$ is prime for the same reason.

May 1st, 2018, 05:38 AM   #24
Newbie

Joined: Mar 2018
From: United States

Posts: 28
Thanks: 2

Quote:
 Originally Posted by cjem This is just a triviality: the multiplicative group of integers modulo $n$ has size less than or equal to $n-1$, with equality if and only if $n$ is prime. So it could only have a subgroup of order $n-1$ if $n$ is prime. There's nothing special about $2$ here. If there is any integer $k$ such that $[n]_k = n-1$, then $n$ is prime for the same reason.
RE: the multiplicative group of integers modulo $n$

How are you defining this for any $n$?

May 1st, 2018, 06:06 AM   #25
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by penrose RE: the multiplicative group of integers modulo $n$ How are you defining this for any $n$?
The set of integers from $1$ to $n-1$ coprime to $n$ with operation given by multiplication mod $n$. (Note that the integers coprime to $n$ are precisely those that have a multiplicative inverse mod $n$. Indeed, let $m$ be an integer. Then Bezout's identity tells us that $n$ and $m$ are coprime if and only if there are integers $x$ and $y$ such that $nx + my = 1$. But this is equivalent to: there exists an integer $y$ such that $my \equiv 1 \pmod n$, i.e. $m$ has a multiplicative inverse mod $n$.)

In the special case that $n$ is prime, every number from $1$ to $n-1$ is coprime to $n$ (i.e. is invertible mod $n$), so the group consists of all of these numbers.

May 13th, 2018, 11:02 AM   #26
Newbie

Joined: Mar 2018
From: United States

Posts: 28
Thanks: 2

Quote:
 Originally Posted by cjem This is just a triviality: the multiplicative group of integers modulo $n$ has size less than or equal to $n-1$, with equality if and only if $n$ is prime. So it could only have a subgroup of order $n-1$ if $n$ is prime. There's nothing special about $2$ here. If there is any integer $k$ such that $[n]_k = n-1$, then $n$ is prime for the same reason.
So indeed if $(n-1)$ mod $[n]_k$ is not $= 0$, $n$ is not prime.

If we look at mod 7, then {1, 2, 3, 4, 5, 6} is a group, and 2 generates {2, 4, 1) while 3 generates the full group. So $[7]_2 = 3$ does not allow us to draw conclusions about 7 being a prime whereas $[7]_3 = 6$ does.

In general, how can we best use the prime divisors of $n-1$ to extract information about $n$?

May 13th, 2018, 12:34 PM   #27
Senior Member

Joined: Aug 2012

Posts: 2,393
Thanks: 749

Quote:
 Originally Posted by penrose If we look at mod 7, then {1, 2, 3, 4, 5, 6} is a group, and 2 generates {2, 4, 1) while 3 generates the full group. So $[7]_2 = 3$ does not allow us to draw conclusions about 7 being a prime whereas $[7]_3 = 6$ does.

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

 May 29th, 2018, 03:13 PM #28 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 True or false? If $p$ is a prime and $2p+1$ is a prime, then $2p+1$ divides $2^p-1$ or $2^p+1$
May 29th, 2018, 04:25 PM   #29
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by penrose True or false? If $p$ is a prime and $2p+1$ is a prime, then $2p+1$ divides $2^p-1$ or $2^p+1$
Sure. As $2p + 1$ is prime, Fermat's little theorem tells us that $2^{2p} - 1 \equiv 0 \pmod{2p+1}$, i.e. $2p + 1$ divides $2^{2p} - 1 = (2^p - 1)(2^p + 1)$. But, again as $2p + 1$ is prime, this implies that $2p+1$ divides $2^p - 1$ or $2^p + 1$.

If you work a little harder, you can say when each case happens: if $p \equiv 3 \bmod 4$ then $2p + 1$ divides $2^p - 1$; if $p \equiv 1 \bmod 4$ then $2p + 1$ divides $2^p + 1$. The only ways I can think of to prove this right now use a small amount of the theory of quadratic residues. If I think of a more elementary approach (at least one that isn't essentially spending a page building up the theory from scratch!) I'll come back and post it.

June 10th, 2018, 10:14 AM   #30
Newbie

Joined: Mar 2018
From: United States

Posts: 28
Thanks: 2

Quote:
 Originally Posted by penrose True or false? If $p$ is a prime and $2p+1$ is a prime, then $2p+1$ divides $2^p-1$ or $2^p+1$
Quote:
 Originally Posted by cjem Sure. As $2p + 1$ is prime, Fermat's little theorem tells us that $2^{2p} - 1 \equiv 0 \pmod{2p+1}$, i.e. $2p + 1$ divides $2^{2p} - 1 = (2^p - 1)(2^p + 1)$. But, again as $2p + 1$ is prime, this implies that $2p+1$ divides $2^p - 1$ or $2^p + 1$.
So it looks like we can drop the original condition on p (if $p$ is a prime).

Given any n, if $2n+1$ is a prime, then $2n+1$ divides $2^n-1$ or $2^n+1$

 Tags factoring, primes

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mobel Number Theory 2 September 21st, 2015 01:44 PM matheist Number Theory 3 October 30th, 2014 05:52 PM caters Number Theory 67 March 19th, 2014 04:32 PM agustin975 Number Theory 11 March 10th, 2013 05:40 AM billymac00 Number Theory 4 November 22nd, 2009 04:05 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top