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
August 30th, 2017, 04:38 PM   #31
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

https://en.m.wikipedia.org/wiki/Tabl...factorizations

A small sample of the above wiki link follows

Note that there are rational primes which are not Gaussian primes. A simple example is the rational prime 5, which is factored as 5=(2+i)(2−i) in the table, and therefore not a Gaussian prime.

So there is sense in trying to reason mathematically on the assumption that 5 is not prime.

I guess you must be the pope , eh my friend?

:
agentredlum is offline  
 
August 31st, 2017, 12:35 AM   #32
Math Team
 
Joined: Apr 2010

Posts: 2,780
Thanks: 361

Quote:
Originally Posted by JeffM1 View Post
If 5 is composite, then there exist positive integers x and y such that x * y = 5. Can you prove that neither x nor y nor any combination of x and y that is an integer divides evenly into 11?
I think so, yes.
gcd(11, 5) = gcd(5, 1) = gcd(1, 0) = 1. So 11 isn't divisible by x nor by y.

I read the of 5 not being prime merely as a change of definition of primes;
"A number is prime iff it has exactly 2 divisors and is unequal to 5. "
But I imagine there's more than one way to read it.

Quote:
Originally Posted by agentredlum View Post
Welcome back Hoempa , missed you buddy ...

Aww, very kind! A lot of people were leaving, glad to see you back agent! Thought you left too

Quote:
Originally Posted by agentredlum View Post
Easy exercise...

Prove that $ \ \ 6 \times 12 + 5 \ \ $ is composite without multiplying it out to get $ \ \ 77 \ \ $

You are not allowed to use $ \ \ 77 \ \ $ in any way.
Hm, 6*12 + 5 = 6*13 - 1 = 6 * (2 * 6 + 2 - 1) - 1 = 2*6*6 - 1*6 + 2*6 - 1 = (6*2 - 1)(6*1 + 1). Right?
Thanks from agentredlum
Hoempa is offline  
August 31st, 2017, 01:43 AM   #33
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
Originally Posted by Hoempa View Post
I think so, yes.
gcd(11, 5) = gcd(5, 1) = gcd(1, 0) = 1. So 11 isn't divisible by x nor by y.
I really like this way of doing the Euclidean Algorithm. Glad you posted it. No division or multiplication necessary just subtraction. I know you subtracted 2*5 but that is a bonus to make the calculation shorter.

You could have done

gcd(11 , 5) = gcd(6 , 5) = gcd(1 , 5) = gcd(1 , 0) = 1

And other paths are possible to get the right answer , switching order inside parenthesis is ok too and I think you did that in steps 2 and 3 right?

Follow up question: Is it possible to write 1 as a linear combination of 11 and 5 using this shortcut or must we go the long way?

Quote:
Originally Posted by Hoempa View Post
I read the of 5 not being prime merely as a change of definition of primes;
"A number is prime iff it has exactly 2 divisors and is unequal to 5. "
But I imagine there's more than one way to read it.
Honestly , I didn't think that far ahead. Your interpretation would just exclude 5 from the list of primes so 11 would still be prime as you posted previously. I was thinking about it in a very abstract way.

Quote:
Originally Posted by Hoempa View Post
Hm, 6*12 + 5 = 6*13 - 1 = 6 * (2 * 6 + 2 - 1) - 1 = 2*6*6 - 1*6 + 2*6 - 1 = (6*2 - 1)(6*1 + 1). Right?
Absolutely Sir. There's an infinite number of ways to prove this easy exercise without using 77 in any way. Here's another way.

$ 6(12) + 5 = 6(11 + 1) + 5 = 6(11)+ 6(1) + 5 = 6(11) + 11 = 7(11) $


Last edited by agentredlum; August 31st, 2017 at 01:52 AM. Reason: boo boo
agentredlum is offline  
August 31st, 2017, 04:36 AM   #34
Global Moderator
 
Joined: Dec 2006

Posts: 20,926
Thanks: 2205

6*12 + 5 = 6*12 + 12 - 6 - 1 = (6 + 1)(12 - 1)
skipjack is offline  
August 31st, 2017, 10:32 AM   #35
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

6*12 + 5 = 6*11 + 11 = 7*11

I can skip steps too.

agentredlum is offline  
August 31st, 2017, 01:51 PM   #36
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

I find this thread incompletely specified.

If we say that the definition of prime is any positive integer that can be divided evenly by only two distinct integers, provided that 5 is defined as not prime, it has been shown that
11 = 6 * 2 - 1 is prime. No problem on my part with that though I admit I interpreted the question differently.

I interpreted it as saying that if there exist positive integers x and y such that x > 1
and y > 1 and x * y = 5, then 6n - 1 is not prime. I have not seen a proof of that conclusion.

I have seen a purported proof starting with the assertion that x must equal 2, 3, or 4 and y must equal 2, 3, or 4. That assertion appears to be based on the normal rules of arithmetic, but clearly the normal rules of arithmetic cannot apply because, if so,
x * y < 5 or x * y > 5. Therefore, we must select a new set of rules. For example, let's say that 2 * 2 = 5, 2 * 3 = 10, 2 * 4 = 17, and 3 * 3 = 13. Lo and behold, 11 must be prime.

This goes back to mashcke's comment that we can prove anything from a false premise. So we can prove that 11 is prime or 11 is not prime if we start from 5 is not prime understood in its normal sense. Unless we are told the rules of an alternative arithmetic in which 5 is not prime, there can be neither proof nor disproof on whether 11, 17, 23, 29, 41 etc are primes. I suspect, that there are sets of arithmetic rules where 5 is composite and 11 is prime and different sets of arithmetic rules where both 5 and 11 are composite. But the rules used in the purported proof are clearly inconsistent.
JeffM1 is offline  
August 31st, 2017, 11:31 PM   #37
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
Originally Posted by JeffM1 View Post
I.... I suspect, that there are sets of arithmetic rules where 5 is composite and 11 is prime ...
Number theory usually is very counter-intuitive. For now , I would like to respond to a small portion of your post reproduced above.

1) in mod 11 , 4*4 = 5 so we can say 5 is composite. Note that 4 < 5 and this ties in nicely with the 'purported' 2 , 3 , 4 'proof' which you found objectionable.

To show 11 is composite you need to find integers

$ 2 \ \le \ a \ , \ b \ \le \ 10 \ \ $ such that

$ (a \times b) \equiv 0 \ \ (\text{mod} \ 11)$

Let me know if you find any

2) In the Gaussian Integers 5 is composite and 11 is prime

$5 \ \ $ is factorable as $ \ \ (2 + i)(2-i) $

There are slightly more complicated reasons why $ \ \ 11 \ \ $ is prime (not factorable) in the Gaussian Integers and it would be best for you to look it up and post questions for discussion if you have any difficulties understanding.
agentredlum is offline  
September 1st, 2017, 04:11 AM   #38
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by agentredlum View Post
1) in mod 11 , 4*4 = 5 so we can say 5 is composite. Note that 4 < 5 and this ties in nicely with the 'purported' 2 , 3 , 4 'proof' which you found objectionable.

To show 11 is composite you need to find integers

$ 2 \ \le \ a \ , \ b \ \le \ 10 \ \ $ such that

$ (a \times b) \equiv 0 \ \ (\text{mod} \ 11)$

Let me know if you find any
When defining what it means to be prime in an integral domain, we exclude the zero element, so $11 \cong_{11} 0$ is just not prime by definition. Furthermore, the integers mod 11 form a field, and there are no prime elements in a field anyway.

By the way, I'd recommend looking up the definitions of "prime" and "irreducible" in integral domains. The definition of prime you're used to actually corresponds to "irreducible"; "prime" is a stronger condition in general (but in the ring of integers and all other UFDs, prime $\iff$ irreducible).

Last edited by cjem; September 1st, 2017 at 04:15 AM.
cjem is offline  
September 1st, 2017, 06:14 AM   #39
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
Originally Posted by cjem View Post
When defining what it means to be prime in an integral domain, we exclude the zero element, so $11 \cong_{11} 0$ is just not prime by definition.
Maybe there is good reason , I won't argue against someone else's definition.

cjem ... look closely at my post. I excluded $ \ 0 \ , \ 1 \ , \ 11 $ from the inequality.

It seems like a convention to say there are no primes in modular arithmetic.

Modular arithmetic has a great deal in common with regular arithmetic , stripped to it's bare bones mechanics it's just regular arithmetic on a clock!

For example , in mod 8 a,b can be found such that

$(a \times b) \equiv 0$

$(2 \times 4) \equiv 0$

note $ 2 \ \le \ 2 \ , \ 4 \ \le 7 $

But I do believe from what I have read that a,b cannot be found if the modulus is prime.

For me , nothing is etched in stone , I question everything.
agentredlum is offline  
September 1st, 2017, 06:50 AM   #40
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by agentredlum View Post
cjem ... look closely at my post. I excluded $ \ 0 \ , \ 1 \ , \ 11 $ from the inequality.
I was talking about the fact that you were trying to show that 11 is composite, not what numbers you had in your inequality; this is not necessary for the two reasons I gave above: 11 is the zero element in $\frac{\mathbb{Z}}{11\mathbb{Z}}$ so can't be prime anyway, and $\frac{\mathbb{Z}}{11\mathbb{Z}}$ is a field, so there aren't any primes at all.

Quote:
Originally Posted by agentredlum View Post
It seems like a convention to say there are no primes in modular arithmetic.
We only tend to define primes in integral domains, i.e. commutative rings with no zero divisors - notions of primality, etc. get very weird when we have zero divisors. When $n$ is prime, the ring $\frac{\mathbb{Z}}{n\mathbb{Z}}$ is a field (so every non-zero element is a unit, and thus not prime); when $n$ is composite, the ring $\frac{\mathbb{Z}}{n\mathbb{Z}}$ is not even an integral domain.


Quote:
Originally Posted by agentredlum View Post
But I do believe from what I have read that a,b cannot be found if the modulus is prime.
Correct. If the modulus $p$ is prime, $p$ does not divide $ab$ for any integers $1 < a,b < p$, so $ab \not \cong 0 \, (mod \, p)$. In other words, there are no zero divisors in the ring of integers mod $p$, so it is an integral domain. However, when the modulus $n$ is composite, you can always find zero divisors (so we never get an integral domain). Indeed, there exist integers $1 < a,b < n$ such that $n = ab$, so $ab = n \cong 0 \, (mod \, n)$.

Last edited by cjem; September 1st, 2017 at 07:13 AM.
cjem is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
claims, euler, finds, identity, pattern, prime, video



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime Pattern Rediscovered HawkI Number Theory 17 April 20th, 2017 10:14 AM
I've had a go at trying to find a pattern to prime numbers HawkI Math 5 June 27th, 2016 07:37 AM
Theory of variable prime pattern KenE Math 1 April 12th, 2016 01:05 PM
Help with Euler's identity; i = 0?? Tau Complex Analysis 5 May 26th, 2015 03:34 AM
Video on prime numbers greg1313 New Users 1 October 9th, 2012 01:35 AM





Copyright © 2019 My Math Forum. All rights reserved.