My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
Reply
 
LinkBack Thread Tools Display Modes
April 20th, 2018, 05:55 AM   #21
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 204
Thanks: 60

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by penrose View Post
Does that proof look okay?
Yep, that's fine.
cjem is online now  
 
April 29th, 2018, 07:36 AM   #22
Newbie
 
Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

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: ???
penrose is offline  
April 30th, 2018, 03:05 AM   #23
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 204
Thanks: 60

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by penrose View Post
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.
cjem is online now  
May 1st, 2018, 05:38 AM   #24
Newbie
 
Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
Originally Posted by cjem View Post
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$?
penrose is offline  
May 1st, 2018, 06:06 AM   #25
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 204
Thanks: 60

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by penrose View Post
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.
cjem is online now  
May 13th, 2018, 11:02 AM   #26
Newbie
 
Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
Originally Posted by cjem View Post
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$?
penrose is offline  
May 13th, 2018, 12:34 PM   #27
Senior Member
 
Joined: Aug 2012

Posts: 1,958
Thanks: 547

Quote:
Originally Posted by penrose View Post
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
Maschke is online now  
May 29th, 2018, 03:13 PM   #28
Newbie
 
Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

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$
penrose is offline  
May 29th, 2018, 04:25 PM   #29
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 204
Thanks: 60

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by penrose View Post
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.
cjem is online now  
June 10th, 2018, 10:14 AM   #30
Newbie
 
Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
Originally Posted by penrose View Post
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 View Post
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$
penrose is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
factoring, primes



Thread Tools
Display Modes


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





Copyright © 2018 My Math Forum. All rights reserved.