/sci/ - Science & Math

It is irreducible for n=1, n=2 and n=3 by inducton it is irreducible for all n.

Can't see shit dickhead

It'd be nice if I could read it with Firefox, but apparently that's not possible and no one wants to translate to LaTex.

Prove that <span class="math">\frac{21n+4}{14n+3}[/spoiler] is irreducible for every natural number <span class="math">n[/spoiler].

>>4899911

>not having 4chanX
>2011 + 0.99999....

>>4899923
Wait how is this a Putnam problem? This looks like a freshman problem... What am I missing?

>>4899923
>Equivalent question:
Show that 4 mod 21 and 3 mod 14 are disjoint sets.

Seems a little too easy...

>>4899934
Is that equivalent? For example 4 mod 6 and 5 mod 9 are disjoint but <span class="math">\frac{6n+4}{9n+5}[/spoiler] is reducible when n = 1.

Anyways here's how I did it.

<span class="math">\gcd(21n+4,14n+3) = \gcd(7n+1,14n+3) = \gcd(7n+1, 1) = 1[/spoiler] by the Euclidean Algorithm so it's always irreducible.

A [truly] equivalent question is:

Prove that the least common multiple of 21n+4 and 14n+3 is 294n^2 + 119n + 12 for all n.

Not sure if it's helpful.

>>4899911
>>4899912
Failing all else, you can right click and press view image info, which will show it with a clear background.

This is actually easy...
>>4899949

>>4899949
Can you explain the steps?

>>4899977
Eudclidean algorithm states that if A>B, gcf(A,B) = gcf(A-B,B).
Do this multiple times to get the result. If the gcf is 1, then they will just keep reducing until either A or B is 1.

reposting yesterday's because nobody wanted to solve it

>>4900000
and LaTeX'd

Show that for each prime <span class="math">p[/spoiler], there exists a prime <span class="math">q[/spoiler] such that <span class="math">n^p - p[/spoiler] is not divisible by <span class="math">q[/spoiler] for any positive integer <span class="math">n[/spoiler].

for x = (21n+4)/(14n+3)
limit of x as n -> 0 is 4/3
limit of x as n -> inf is 3/2
there are no integers between 3/2 and 4/3 thus x is irreducible

That doesn't mean it's irreducible.

Like 4/6 -> 2/3

>>4900038
meant to quote >>4900014

>>4899986
How does the Euclidean Algorithm imply
gcf(A,B) = gcf(A-B,B)?

It says that if a = bq + r, 0 <=r < b, then
gcd(a,b) = gcd(b, r) = gcd(b, a-bq).

You must prove that q is 1 in each case.

>>4900191
It implies that because if a number divides into two numbers, it MUST divide into their difference. Otherwise there would be no way to get from the smaller number to the larger number

>>4900191
i.e. 27 and 45. Let's pretend we don't know that they're both divisible by 9. Whatever their gcf is MUST go into 18, otherwise it would not be a common factor.

>>4900209
I get that. But can someone prove this:

gcd(b, a-bq) = gcd(b, a-b), where
a = bq + r

say it is not irreducible, then 21n+4 is multiple of 14n+3
so there is an integer k >= 1 such that (14n+3)k = 21n+4

14kn+3k = 21n+4
14kn-21n = 4-3k
(14k-21)n = 4-3k
7n(2k-3) = 4-3k
7n = (4-3k)/(2k-3)

n is natural so 7n>0 (n cant be 0 cuz 4/3 is not reducible)
k must be greater than 1 cuz theres no way that 21n+4 will be negative for n natural, and 14n+3 cant be negative either, also theres no way 21n+4 will be 0

0 < 7n = (4-3k)/(2k-3)
k = 1 doesnt work, for k = 2,3 and so on, 4-3k will be negative, and 2k-3 will be positive
so ur saying 0 is smaller than a negative number
0 < 7n = (4-3k)/(2k-3) < 0
0 < 0
contradiction
therefore (21n+4)/(14n+3) is irreducible for every natural number n

>>4900563
lol this is wrong ignore it

>>4900000

Dem quints

>>4900255
If no one can, then the gcd proof is null.

>>4900859
I don't think we need to. In fact, the proof at
>>4899949
uses what's said here
>>4900191
>It says that if a = bq + r, 0 <=r < b, then
>gcd(a,b) = gcd(b, r) = gcd(b, a-bq)

first: euclidian fucking division

21n+4=14n+3 + (7n+1)

14n+3=2*(7n+1)+1

therefore gcd(21n+4, 14n+3)=1 for all n.
Therefore the fraction is irreductible.

>>4900879

>euclidian

>>4900584
>>4900000
Quints confirms it: mods need to bring back the Putnam sticky.

>>4900859
>>4900255
>gcd(b, a-bq) = gcd(b, a-b), where a=bq+r
simplest high school proof:
let's note d=gcd(b,a-b)
b=k.d
a-b=l.d
therefore a=a-b+b=l.d+k.d=(k+l).d
and a-bq=(k+l)d-k.q.d=(k+l-kq)d

therefore d divides a-bq.
so gcd(b,a-bq) divides gcd(b,a-b)
by a symetrical reasoning, gcd(b,a-b) divides gcd(b,a-bq).
Therefore both gcd are equal.

Alright we've beat the OP to death.

get to work on
>>4900000
>>4900000
>>4900000

>>4900000
for p=2, q=3
for n=0, n^2-2 = -2 = 1 mod 3
then it increases +1,+3,+5,+7,+9...
which is 1 mod 3, 0 mod 3, 2 mod 3, 1 mod 3, 0 mod 3, 2 mod 3, ... repeating
so when -2 = 1 mod 3 is summed to 1 mod 3, it becomes 2 mod 3
then it is added 0 mod 3, it remains 2 mod 3,
then it is added 2 mod 3, and it gets back to 1 mod 3
and the process repeats, so it will never be 0 mod 3, so it will never be divisible by 3

>>4900892
http://archive.installgentoo.net/sci/thread/S4875845
It wasn't a mod.

It has come to my attention that this works because all the integers generated by integer input to the polynomials in both numerator and denominator are prime - I am working on a proof, I think my work might imply RH.