Math Help Forum - Number theory

Math Help Forum - Number theory http://www.mathhelpforum.com/math-help en Fri, 20 Nov 2009 23:56:04 GMT vBulletin 60 http://www.mathhelpforum.com/math-help/images/MHF/misc/rss.jpg Math Help Forum - Number theory http://www.mathhelpforum.com/math-help Getting stuck on the CRT http://www.mathhelpforum.com/math-help/number-theory/115803-getting-stuck-crt.html Fri, 20 Nov 2009 22:02:38 GMT Ok, here's the problem.
x

2 (mod 5)
x

1 (mod 7)
x

3 (mod 11)

Here is what I have so far..

M=5x7x11=385

M1=385/5=77
m2=385/7=55
M3=385/11=35

x=(a1xM1xy1)+(a2xM2xy2)+(a3xM3xy3)

77y1

1 (mod 5)
55y2

1 (mod 7)
35y3

1 (mod 11)

The issue I am having is getting the correct numbers for y1,y2,y3. What I am doing is using the Extended Euclidean Algorithm, but I'm not getting the numbers that are shown in my book, so I'm thinking that using the Extended Euclidean Algorithm isn't the proper way to figure out what the y's are. SO for example..I know that the solution to 77y1

1 (mod 5) is 3(mod 5), I just don't know where the 3 is coming from.

I hope this has all made sense, I explained this as clearly as possible!! Thanks for the help! ]]> Number theory steph3824 http://www.mathhelpforum.com/math-help/number-theory/115803-getting-stuck-crt.html Numbers in array and its exponents ( congruence operation ) http://www.mathhelpforum.com/math-help/number-theory/115793-numbers-array-its-exponents-congruence-operation.html Fri, 20 Nov 2009 21:21:27 GMT Introduction: ============= Another way to see congruences is to put the numbers in an array of width n. In the following example n is 5: col 1 2 3 4 5 -------------------------- 1 2 3 4 5 6 7 8 9 10 Introduction:
=============

Another way to see congruences is to put the numbers in an array of width n.
In the following example n is 5:

col 1 2 3 4 5
--------------------------
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35
36 37 38 39 40

Numbers in the same column are congruent module 5, for instance 13 and 18
are in the same column (3) so they are congruent mod 5,
both gives 3 as a remainder when divided by 5.

This way is very simple to see how some congruence operations work,
for instance, two numbers will go together to the same column if I add a number x to
them ( if x is 3, then 13+3=16 and 18+3 is 21, 16 and 21 now are on column 1 )

What I am interested in:
========================

Lets look at the exponent operation, get number 2 in the table above, it is
on column 2, now lets see in what columns 2^x result lands:

2^1 = 2 ( column 2)
2^2 = 4 ( column 4)
2^3 = 8 ( column 3)
2^4 = 16 ( column 1)
2^5 = 32 ( column 2)

The results landed in all possible columns, except 5, before it went back to
its initial column 2.

I read that if the number I chose is coprime with n ( 2 and 5 are coprime in
my example ) the exponent results would land in all possible columns (except n)
before repeating a column.

Question:
=========

How can this be proved ?

Thanks,
]]> Number theory jmarchetti http://www.mathhelpforum.com/math-help/number-theory/115793-numbers-array-its-exponents-congruence-operation.html pythagorean triangles. http://www.mathhelpforum.com/math-help/number-theory/115780-pythagorean-triangles.html Fri, 20 Nov 2009 20:13:47 GMT prove 12 divides product of legs prove 60 divides product of sides prove 12 divides product of legs

prove 60 divides product of sides ]]> Number theory stumped765 http://www.mathhelpforum.com/math-help/number-theory/115780-pythagorean-triangles.html Prove by contradiction http://www.mathhelpforum.com/math-help/number-theory/115764-prove-contradiction.html Fri, 20 Nov 2009 17:55:20 GMT Prove by contradiction that if r is irrational, then r^(1/2) is irrational Prove by contradiction that if r is irrational, then r^(1/2) is irrational ]]> Number theory hebby http://www.mathhelpforum.com/math-help/number-theory/115764-prove-contradiction.html Prove by contradiction http://www.mathhelpforum.com/math-help/number-theory/115762-prove-contradiction.html Fri, 20 Nov 2009 17:49:35 GMT Prove by contradiction that 2^(1/3) is irrational. I made a=2^(1/3). a^2= 2^(2/3) then 2^(2/3)= _M^2 _ because we assume a is rational N^2 then what do I do Prove by contradiction that 2^(1/3) is irrational.

I made a=2^(1/3).

a^2= 2^(2/3)

then 2^(2/3)= M^2 because we assume a is rational
N^2
then what do I do ]]> Number theory hebby http://www.mathhelpforum.com/math-help/number-theory/115762-prove-contradiction.html one more quadratic residue congruence problem please http://www.mathhelpforum.com/math-help/number-theory/115738-one-more-quadratic-residue-congruence-problem-please.html Fri, 20 Nov 2009 14:30:43 GMT ---Quote--- Prove that if p is an odd prime then x^2\equiv 2\mod p has solutions if and only if p\equiv1 or 7\mod 8. ---End Quote--- This exercise comes in the chapter on quadratic residues and the Legendre symbol. I have absolutely no idea how to prove what it asks. None of the theorems in...

Quote:

Prove that if $p$ is an odd prime then $x^2\equiv 2\mod p$ has solutions if and only if $p\equiv1$ or $7\mod 8$ .

This exercise comes in the chapter on quadratic residues and the Legendre symbol. I have absolutely no idea how to prove what it asks. None of the theorems in the chapter seem relevant.

My professor has been skipping around in the book, and blending in his own material. I suspect he may have skipped over something from an earlier chapter, which I need to solve this.

Hints or useful theorems would be much appreciated. ]]> Number theory hatsoff http://www.mathhelpforum.com/math-help/number-theory/115738-one-more-quadratic-residue-congruence-problem-please.html <![CDATA[[SOLVED] quadratic residues congruence problem]]> http://www.mathhelpforum.com/math-help/number-theory/115639-solved-quadratic-residues-congruence-problem.html Thu, 19 Nov 2009 23:23:37 GMT

Quote:

list all solutions of...the ten congruences $x^2\equiv a\mod 11^2$ where $a=1,3,4,5,9$ .

We know that each congruence has two solutions, and that if we can find one solution $x\equiv s$ then the second solution is $x\equiv-s$ . But I don't know any algorithms I can use to solve each of the first solutions, except trial and error, which of course is far too inefficient.

This is an exercise in the chapter for quadratic residues, so presumably that has something to do with it.

Any ideas would be appreciated. ]]> Number theory hatsoff http://www.mathhelpforum.com/math-help/number-theory/115639-solved-quadratic-residues-congruence-problem.html Linear Congruences http://www.mathhelpforum.com/math-help/number-theory/115582-linear-congruences.html Thu, 19 Nov 2009 16:04:08 GMT 5, the following system has a solution: 7x + 3y = 1 mod p 4x + 6y = -1 mod p]]> How do i prove that for every prime p > 5, the following system has a solution:

7x + 3y = 1 mod p
4x + 6y = -1 mod p ]]> Number theory Zero266 http://www.mathhelpforum.com/math-help/number-theory/115582-linear-congruences.html Solve congruence using primitive root http://www.mathhelpforum.com/math-help/number-theory/115549-solve-congruence-using-primitive-root.html Thu, 19 Nov 2009 10:56:24 GMT Hi, I have to solve this congruence

$y^5 \equiv -1(mod22)$

Now i've worked out that 7 is a primitive root mod 22. And y=7 is a solution. But shouldn't there be 5 solutions? How do I find the rest?

I have tried using the fact that because (y,22)=1 if y is a solution, then

$y \equiv{7^k}(mod22)$

to give me

$7^{5k} \equiv{-1}(mod22)$

but i'm not sure if this gets me anywhere,

Please help.
Katy :) ]]> Number theory harkapobi http://www.mathhelpforum.com/math-help/number-theory/115549-solve-congruence-using-primitive-root.html Set theory clarification http://www.mathhelpforum.com/math-help/number-theory/115478-set-theory-clarification.html Thu, 19 Nov 2009 01:36:27 GMT A = { a, b, c, d, e, f, g} Expression: x = y such that x, y are in A can x in A refer to the same thing as y in A or can it necessarily not because of the notation x, y in A? A = { a, b, c, d, e, f, g}
Expression: x = y such that x, y are in A

can x in A refer to the same thing as y in A or can it necessarily not because of the notation x, y in A? ]]> Number theory Noxide http://www.mathhelpforum.com/math-help/number-theory/115478-set-theory-clarification.html <![CDATA[[SOLVED] Valid Proof? I DONT THINK SO...]]> http://www.mathhelpforum.com/math-help/number-theory/115449-solved-valid-proof-i-dont-think-so.html Wed, 18 Nov 2009 23:37:58 GMT How the heck is the following a valid proof for: Show that the relation R on the integers defined by (x, y) in R if and only if y = 2x is antisymmetric Proof: Suppose (x, y) in R and (y, x) in R To show: x = y Since (x,y) in R , y = 2x How the heck is the following a valid proof for:

Show that the relation R on the integers defined by (x, y) in R if and only if y = 2x is antisymmetric

Proof:

Suppose (x, y) in R and (y, x) in R
To show: x = y

Since (x,y) in R , y = 2x
Since (y, x) in R, x = 2y
therefore y = 2x = 2(2y) = 4y

THE FOLLOWING MAKES NO SENSE AT ALL

therefore 3y = 0
therefore y = 0
therefore x = 2y = (2)(0) = 0
therefore x = y , and R is antisymmetric

This makes no sense at all. AT ALL.
I other than 0,0 i cannot find a pair in this relation that would be antisymmetric...
is a whole freaking relation antisymmetric if i can find one pair in it that is?
So frustrated.

PLEASE HELP ]]> Number theory Noxide http://www.mathhelpforum.com/math-help/number-theory/115449-solved-valid-proof-i-dont-think-so.html Need help understanding the Chinese Remainder Theorem http://www.mathhelpforum.com/math-help/number-theory/115429-need-help-understanding-chinese-remainder-theorem.html Wed, 18 Nov 2009 22:46:42 GMT Here is a simple example. xImage: http://www.mathhelpforum.com/math-help/latex2/img/851ffc531f462fd9c1fd2bcc1340c453-1.gif (http://www.mathhelpforum.com/math-help/JSREPL98326:;) 11 (mod 39) xImage: http://www.mathhelpforum.com/math-help/latex2/img/851ffc531f462fd9c1fd2bcc1340c453-1.gif ... Here is a simple example.

x

11 (mod 39)
x

7 (mod 22)

I would greatly appreciate it if someone could explain how to do this. I know first of all that 39a+22b=1. I believe you are supposed to use Euclid's Algorithm right? I know how to do Euclid's Algorithm I just don't understand how to use it to solve the problem I have shown above. Please explain as much as you can, big test coming up soon! ]]> Number theory steph3824 http://www.mathhelpforum.com/math-help/number-theory/115429-need-help-understanding-chinese-remainder-theorem.html Prove x^4 - x^2 + 1 is reducible over F_p for all p http://www.mathhelpforum.com/math-help/number-theory/115420-prove-x-4-x-2-1-reducible-over-f_p-all-p.html Wed, 18 Nov 2009 21:50:51 GMT 3 but can't seem to...]]> Prove that $x^4 - x^2 + 1$ is reducible over $\mathbb{F}_p$ for every prime $p$ .

I know $x^4 - x^2 + 1$ is the 12th cyclotomic polynomial and know a few properties of such polynomials, but I'm not sure if that really helps here. I can also show that $p^2 -1$ is divisible by 12 for $p>3$ but can't seem to make use of that (although have been given a hint that this would be useful). ]]> Number theory Boysilver http://www.mathhelpforum.com/math-help/number-theory/115420-prove-x-4-x-2-1-reducible-over-f_p-all-p.html Not a power of 2 http://www.mathhelpforum.com/math-help/number-theory/115407-not-power-2-a.html Wed, 18 Nov 2009 20:32:50 GMT 1 (n,k\in\mathbb{Z^+}).]]> Show that $k^n+k^{n-1}+\ldots +k+1$ can't be a power of 2 if $k>1$ ( $n,k\in\mathbb{Z^+}$ ). ]]> Number theory james_bond http://www.mathhelpforum.com/math-help/number-theory/115407-not-power-2-a.html prove irrational http://www.mathhelpforum.com/math-help/number-theory/115394-prove-irrational.html Wed, 18 Nov 2009 19:22:40 GMT prove that sin(1) (one radian) is irrational. Hint start with taylor series expansion prove that sin(1) (one radian) is irrational.
Hint start with taylor series expansion ]]> Number theory scubasteve123 http://www.mathhelpforum.com/math-help/number-theory/115394-prove-irrational.html