User Name Remember Me? Password

 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 $_2 = 3$. If we look at the prime number 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 $_2 = 3$ does not allow us to draw conclusions about 7 being a prime whereas $_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 $_2 = 3$ does not allow us to draw conclusions about 7 being a prime whereas $_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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      