elementary-number-theory

[brittle patrol]

yeah exactly one of them is even

[lunar quiver]

let x =2a let b=2b+1

letx=2a y=2b+1

[hazy hawk]

Both can be odd

[lunar quiver]

true

still check all cases not difficult
x = 2a y =2b+1
2a(2b+1)(2a+2b+1)=22222.2222

[hazy hawk]

I got that x,y=2(mod 3)

[lunar quiver]

a(2b+1)(2a+2b+1) = 1111...111

where a is odd

2b+1 is odd

[hazy hawk]

Is there a way to write 22...222 in a way that i can insert it into wolfram

[lunar quiver]

just draw a graph with a and b axis to solve

[brittle patrol]

$\frac{2}{9} (10^{2018}-1)$

[sterile pumice]

Gonzo17:

[hazy hawk]

Thanks

[stuck lintel]

how do you solve this >.>

[lethal jay]

Solve wot?

[stuck lintel]

Solve for integers xy(x+y)=2222..22(a number consisting of 2018 twos)

[faint whale]

[astral fiber]

any good books for introductory number theory

[naive temple]

@stuck lintel you can factor that term there

as the difference of some squares

and that kinda helps

not sure thooo

the 9 there is being annoying

but you can write $$2(10^{1009}-1)(10^{1009}+1)$$ which has the xy(x+y) form

[sterile pumice]

cardiou:

[naive temple]

but that's not exactly your problem

[wild zinc]

you can maybe get something from the fact that 10^1009-1 and 10^1009+1 are coprime

alternatively you have a quadratic and you could try solving for x in terms of y

x^2y + xy^2 - 2222...222 = 0, x = (-y^2 +/- sqrt(y^4-8888...888y)/(2y)

so you need sqrt(y^4-8888...888y)/(2y) to be an integer

or (y^2 - 8888...888/y) = 4k^2 for some integer k

(y-2k)(y+2k) = 8888...888/y

idk if that's any easier but potentially

you need y | 8888...888 and (y-2k)(y+2k) | 8888...888

[graceful notch]

[dense pecan]

how do I prove that 2^(16n) will always end in 6

@cyan mango

any hints or tips?

@shrewd marsh

[unkempt hedge]

@dense pecan
2^(16n) = 4^(8n) = 16^(4n)
16^(4n) == 6^(4n) mod(10) (because of binomial theorem)
6^a == 6 mod(10) where a is an positive integer
because 6*6 = 36 == 6 (mod 10)
so
2^(16n) == 6 (mod 10)

[dense pecan]

thanks @unkempt hedge

[unkempt hedge]

np, tell me if there is something you do not understand 😃

[dense pecan]

yeah i'll tag you if I don't understand something, thanks again

@unkempt hedge

Can I prove using fermat's little theorem

oh nvm I figured it out

[unkempt hedge]

well it is the same as last problem

just need to prove that it ends with 6

or 1

and because the exponent 2^m where m is a product of many 2 then it will always end with 6 therefore you can say that it is congruent to 1 mod 5

[dense pecan]

or I can prove that in 2^x x is always divisible by 4 therefore by fermants theorem mod 5 will always be 1

[unkempt hedge]

yes, same thing

[dense pecan]

thanks

[unkempt hedge]

but I didn't do anything

[stuck lintel]

Derive all integer solutions to x^3 + y^3 = z^2

[sacred junco]

Random thought: factor the left side?

[naive temple]

1 2 3 is one

[sacred junco]

Nice

[dense pecan]

Consider the equation 27x + 14y + 10z = 1. Give parameterized solutions for all integer solutions x, y, z. How many parameters do you need? Hint: What does this equation represent, geometrically?

how do I give parameterized solutions for all Integer solutions

@unkempt hedge

is it a,b, (1-27a-14b)/10 ?

[unkempt hedge]

@dense pecan I haven't done this before...

Looks really interesting though

[naive temple]

Hmmm that's doesn't seem guaranteed to be an integer for all a,b

for a=2 and b =1 it isn't

Derive all integer solutions to x^3 + y^3 = z^2

Hmmm Factoring gives

$$ (x+y)(x^2-xy+y^2) = z^2$$

[sterile pumice]

cardiou:

[naive temple]

that's a positive definite quadratic

so x+y must be positive

[unkempt hedge]

@dense pecan
lets consider the homogenous version of "27x + 14y + 10z = 1":
27x + 14y + 10z = 0
then we have the solutions
(0,0,0)
(0,5,-7)
(10,0,-27)
so in the homogenous version we have:
v = v_0 + n u_1 + m u_2
u_1 =[0,0,0] - [0,5,-7] = [0,-5,7]
u_2 = [0,0,0] - [10,0,-27] = [-10,0,27]
v_0 = [0,0,0]
then with out particular solution v_p:
consider, z = 0:
27x + 14y = 1
this has the solution
(-1,2,0)
so v_p = [-1,2,0]
therefore we can say that

x = -1 - 10m
y = 2 - 5n
z = 7n + 27m

I looked it up online
https://math.stackexchange.com/questions/1824353/how-to-find-all-positive-integer-solutions-of-a-diophantine-equation
really fun, and interesting method.
but I cannot promise that I found all the solutions with this method. Because as I stated previously I haven't done this before

[wild zinc]

for x^3+y^3 = z^2

my thoughts are find some restriction on gcd(x,y)

then use that to find some restriction on gcd(x+y,x^2-xy+y^2)

or maybe an assumption on gcd(x,y) could work

made a little harder because it's not homogeneous but it could still work

[wide shuttle]

there are no integer solutions... fermats last theorem

[wild zinc]

...

[brittle patrol]

it's x^3+y^3=z^2 not z^3

[wide shuttle]

o

i blime bad visione

i'd think that you'd have x^3 = a^2, and y^3 = b^2

then look into the pythagorean triples from there

[past summit]

It's pretty easy showing that (x,y,z) being a solution implies (a^2x, a^2y, a^3z) is a solution

And as stated above you can generate Pythagorean tripleets

So you'd get families of Pythagorean triples and their scaled up families

But I think there might be other "families" of solution

[brittle patrol]

if x=dk and y=dl we would need $d^3(k^3+l^3)$ to be a square

[sterile pumice]

Gonzo17:

[brittle patrol]

which is equivalent to $d(k^3+l^3)$ being a square

[sterile pumice]

Gonzo17:

[brittle patrol]

so you can just choose a pair of relatively prime numbers k, l and d would have to be any number completing k^3+l^3 to a square

[past summit]

Ooh interesting

[stuck lintel]

good ideas but any idea on how to generate all solutions?

[sacred junco]

https://gyazo.com/f66d9585a50eba1cd44e3bec4b29c132

[neon comet]

number theory

[swift shard]

I'm thinking they want 165cm = 1m and 65cm

[sacred junco]

Hmm I'll put that in

and see if it correct

[neon comet]

Roide

[sacred junco]

Thx Kaynex

[neon comet]

https://en.wikipedia.org/wiki/Metric_prefix

[sacred junco]

what a stupid question

I was technically right but didn't understand how to answer the question

so I didn't get why my answers were wrong

[swift shard]

Yeah, that's a problem with these web-assigns. Happens a lot

[neon comet]

the purpose is for you to get introduced to the metric system i think

not the actual answers themselves

[sacred junco]

also they want me to remember the measurements

[swift shard]

Question 3 needs the same thing. I think you got question 2 though

[sacred junco]

All questions were 100% correct after changing question 1 and 3

Thx

damn I learned something new

Kilo = 1,000

[swift shard]

Np. In the future, if you don't know what kind of "math" you may be doing, the question channels below are commonly used and can take any question

[sacred junco]

NBA 2K17 kinda similar K = 1,000

[swift shard]

You may have heard of kilometres, or kilograms before

[sacred junco]

https://gyazo.com/15b0a9295c87a9e515b6297b0ddf645a

What the max Ibs in a stone?

Like the maximum last 2 units in feet(height) is 11 for example 5,11

[swift shard]

Oh wow, it's been a while since I've heard of a "stone". I have no idea how many lbs are in a stone

Google is your friend for odd units like that

[sacred junco]

It 14 Ibs

figured out since 14 Ibs = 1 Stone

Thx Kaynex

[swift shard]

I did nothing on that one! Good job

[dense pecan]

so X(n+1) = 4^(n+1) for inductive step

X(n+1) = 3(Xn) + 2(X(n-1))

then 3(Xn) + 2(X(n-1) <= 4^(n+1)

Xn <= 4^n

substitution will get 3(4^n) + 2(4^(n-1)) <= 4^(n+1)

am I going in right direction?

@elder bobcat

[sacred junco]

https://gyazo.com/bd8526339aa30e9dc8f4d1f0ccd32384

nvm I understand it

1500

Im sleeping whilst doing these questions xD

[dense pecan]

@past summit

[dense pecan]

@unkempt hedge

[unkempt hedge]

@dense pecan
X_0 <= 4^0
our hypothesis is that
3X_(n-1) + 2X_(n-2) <= 4^n

and we need too prove that:
3X_(n-2) + 2X_(n-3) <= 4^(n+1)

3X_(n-2) + 2X_(n-3) <= 4(3X_(n-1) + 2X_(n-2))
2X_(n-3) <= 12X_(n-1) + 5X_(n-2)
2X_(n-2) <= 12X_(n-1) + 5X_(n-2)
0 <= 12X_(n-1) + 3X_(n-2)
which is obviously true...

(I haven't learned this formally (self learned), so don't take my word as truth)

[dense pecan]

thanks

[unkempt hedge]

I think you need to check that X_3 is true aswell because my solution utelizes X_(n-1) and X_(n-2)

@dense pecan tbh, it would be easier to just find the equation for X_n and see that it is always less than 4^n

X_n = r^2
r^n = 3r^(n-1) + 2r^(n-2)
r^2 - 3r - 2 = 0
(r-2)(r-1) = 0
then the generall solution to the equation would be

X_n = a 2^n + b 3^n
to find a and b you could use X_0 and X_1
a 2^0 + b 3^0 = 1
a + b = 0

a * 2 + b * 3 = 2 =>
b = 2
a=-2

therefore
X_n = -2 * 2^n + 2 * 3^n
X_n = 2 * 3^n - 2^(n+1)

We need to prove that
2 * 3^n - 2^(n+1) <= 4^n

so

3^n <= 4^n
3^n <= 2^n * 2^n
3^n <= 2^(n-1) * 2^n + 2^n
2 * 3^n <= 2^n * 2^n + 2 * 2^n
2 * 3^n <= 4^n + 22^n
2 * 3^n - 22^n <= 4^n
2 * 3^n - 2^(n+1) <= 4^n
X_n <= 4^n

[past summit]

@dense pecan Use strong induction. Assume it's true for all values up to k. Then

X_k < 4^k
X_k-1 < 4^k-1

Then X_k+1 < 3(4^k) + 2(4^k-1) < 3(4^k) + 4(4^k-1) = 4^k+1

[upbeat pivot]

I'm a bit confused
My middle school teacher gave us hard hwk (I'm only 11 but my iq is 420)
We're supposed to show that this thing called the Riemann zeta function has no zeros of some weird critical line but I'm struggling a bit. Don't worry if you can't understand, i know it's hard 😎
How would I do this?

[brittle patrol]

Lol

[lusty cobalt]

lmao

[dense pecan]

lel

[sturdy dirge]

Share data.

[wild zinc]

this is trivial

why can't you do this at 11

[upbeat pivot]

im sorry

dont worry i finally figured it out

i used this thing called the "fine structure constant"

you probably haven't heard of it, i'd be suprised if you low plebians had 😎
only took me seven lines of working and a lot of hand waving with the todd function
i was just being a little slow it happens to even big boys like me

[naive temple]

go back you your cave, old man

[sacred junco]

Tf xD

[lunar quiver]

Can you help me understand Fermat's Last Theorem then?
Fermat's Last Theorem n=3
a^n +b^n =c^n
a^3+b^3=c^3
let c = 2z+1
8z^3 +12z^2+6z+1 = (2z+1)^3
let b = 2z
b^3 = 8z^3
b^3 + 12z^2+6z+1=c^3
a^3 = 12z^2+6z+1
greatest common dominator between
c and b is 1
Only valid solution to a is when z =0
Extend c = 2z+1, 2z+3, 2z+5,...
Parity is odd + even = odd

[dense pecan]

@past summit @unkempt hedge thanks I get it now

[dense pecan]

I know this is true but how do I start the proof?

@unkempt hedge

[stuck lintel]

Try deriving a closed form for the nth term

[dense pecan]

yeah thanks

will it be nth = (1/4) (Yn-1) - (1/2) (Yn-2) - (3/4)(Yn-3) ?

nth = Sn - Sn-1

[past summit]

Induction

Try proving it by induction

[dense pecan]

yeah thanks and is my nth term correct?

[past summit]

No because at n = 100 it would be 100 terms long

But that's not how you should go about it

Prove it true for the base case

Assume it's true for all values of n up to k

Then show it's true for n=k+1

[dense pecan]

so n=k+1 will be (1/4) Yk + (3/4) Yk-1

replacing k with k+1

[past summit]

So you've assumed that Y_k and Y_k-1 are between 1 and 2

Then using Y_k+1 = 1/4Y_k + 3/4Y_k-1

Show why Y_k+1 is between 1 and 2

[dense pecan]

So you've assumed that Y_k and Y_k-1 are between 1 and 2 -> I think we only assumed Y_k is between 1 and 2

@past summit

[past summit]

It's called strong induction when you do what I said but it's still valid

[dense pecan]

oh

can I just replace Y_k and Y_k-1 with 1 and then 2

min value of Y_k+1 can be at when Y_k and Y_k-1 is 1

max value of Y_k+1 can be at when Y_k and Y_k-1 is 2

@past summit

[past summit]

You could reason it that way

[dense pecan]

what might be the other way

?

Can I assume Y_k-1 will be between 1 and 2 cause if yes than I can also assume Y_k+1 will be between 1 and 2 at the very beginning and there's no need to prove anything

@past summit

[past summit]

Yeah you can

But you should be a bit more formal mathematically when you explain it

[dense pecan]

yeah

[dense pecan]

The above result suggests that this sequence grows in the worst case exponentially, i.e., X_n = O(4^n). Consider trying to tighten this bound in the following way: what are the smallest values α and β such that the above proof still works for ∀n ≥ 0 : Xn ≤ α ∗ β^n? Give the tightest bounds on X_n you can.

@past summit

@vast vessel

[brittle patrol]

so you know you're gonna try to prove it by induction

[dense pecan]

by induction?

I have to fine a smaller bound than 4^n

[brittle patrol]

is that not how you bounded it by 4^n ?

[vast vessel]

"tightest bounds"

upper bounds?

not lower bounds?

[dense pecan]

I meant tighest

[vast vessel]

also what about finding exact formulae for X_n?

that doesn't answer the question

Upper or lower bounds?

[dense pecan]

also what about finding exact formulae for X_n? ---> ?

[vast vessel]

don't gimme "steak" as an answer to a "what's ur favourite smoothie" question

and ya you can get exact formulae

The method is basically to look at the recursive equation and assume the general form you wrote

$$X_n=3X_{n-1}+2X_{n-2};~X_n=\alpha\cdot\beta^n$$

[sterile pumice]

Simple_Art:

[vast vessel]

If you plug this in and simplify, you should get this equation:

$$\beta^2=3\beta+2$$

[sterile pumice]

Simple_Art:

[dense pecan]

how

[vast vessel]

what do you get when you plug it in and simplify?

[dense pecan]

B = 2

B = 3

[vast vessel]

no I mean

what do you get when you plug $X_n=\alpha\cdot\beta^n$ into the equation and simplify

[sterile pumice]

Simple_Art:

[dense pecan]

3alpha beta^x-1 + 2aplha beta^x-2

$$ 3alphabeta^{x-1} + 2aplhabeta^{x-2} $$

[sterile pumice]

qwerty.:

[vast vessel]

what do you get when you plug it into the equation (a thing involving an equal sign)

[sturdy dirge]

Use \alpha, \beta.

[dense pecan]

$\alpha \beta^{n} = 3X_{n-1}+2X_{n-2};$

[sturdy dirge]

One $ per side is enough.

[sterile pumice]

qwerty.:

[vast vessel]

plug it in for all of the X's

[dense pecan]

$\alpha \beta^{n} =3 \alpha \beta^{n-1} + 2 \alpha\beta^{n-2} $

[vast vessel]

what's x?

[dense pecan]

number of recursive calls?

[vast vessel]

$$X_n=3X_{n-1}+2X_{n-2};~X_n=\alpha\cdot\beta^n$$

[sterile pumice]

Simple_Art:

[vast vessel]

where's x?

check your exponents, they don't match up

[sterile pumice]

qwerty.:

[vast vessel]

okay

so now you cancel like factors from both sides

[dense pecan]

how?

[vast vessel]

what's a factor of both sides that you can divide by?

[dense pecan]

\alpha

[vast vessel]

okay

then cancel it

[dense pecan]

$\beta^{n} =3 \beta^{n-1} + 2 \beta^{n-2}$

[sterile pumice]

qwerty.:

[vast vessel]

Okay

and by exponent rules:

$\beta^n=?\cdot\beta^{n-2}$\$\beta^{n-1}=?\cdot\beta^{n-2}$

[sterile pumice]

Simple_Art:

[dense pecan]

$\beta^{-2}$

[sterile pumice]

qwerty.:

[dense pecan]

$\beta^{-1}$

[sterile pumice]

qwerty.:

[vast vessel]

no

$\beta^{-2}\cdot\beta^{n-2}=\beta^{n-4}$

[sterile pumice]

Simple_Art:

[vast vessel]

you want to get to $\beta^n$ and $\beta^{n-1}$

[sterile pumice]

Simple_Art:

[vast vessel]

$\beta^x\cdot\beta^y=\beta^{x+y}$

[sterile pumice]

Simple_Art:

[vast vessel]

what do you need to add to n-2 to get to n?

[dense pecan]

$\beta^{-2}$

[sterile pumice]

qwerty.:

[vast vessel]

no

$\beta^{-2}\cdot\beta^{n-2}=\beta^{-2+n-2}=\beta^{n-4}\ne\beta^n$

[sterile pumice]

Simple_Art:

[dense pecan]

$\beta^{-2}\cdot\beta^n=\beta^{n-2}$

[vast vessel]

yes, but that was not the question...

[sterile pumice]

qwerty.:

[vast vessel]

correct answers to the wrong question my man

[dense pecan]

where did this come from?

$\beta^{-2}\cdot\beta^{n-2}=\beta^{-2+n-2}=\beta^{n-4}\ne\beta^n$

[sterile pumice]

qwerty.:

[vast vessel]

I asked what you multiply $\beta^{n-2}$ by to get $\beta^n$

[sterile pumice]

Simple_Art:

[vast vessel]

And you said $\beta^{-2}$

[sterile pumice]

Simple_Art:

[dense pecan]

oh

+2

[vast vessel]

Okay

[sterile pumice]

Simple_Art:

[vast vessel]

What do you need to get to $\beta^{n-1}$?

[sterile pumice]

Simple_Art:

[dense pecan]

from $\beta^{n}$ ?

[sterile pumice]

qwerty.:

[vast vessel]

$\beta^{n-1}=(?)\cdot\beta^{n-2}$

[sterile pumice]

Simple_Art:

[vast vessel]

fill in the (?)

[dense pecan]

$\beta^{1}$

[sterile pumice]

qwerty.:

[vast vessel]

okay

so back to what you said earlier:
https://discordapp.com/channels/268882317391429632/418981682117345288/525846059176689680

$$\beta^n=3\beta^{n-1}+2\beta^{n-2}$$

[sterile pumice]

Simple_Art:

[vast vessel]

This becomes:

$$\beta^2\cdot\beta^{n-2}=3\beta\cdot\beta^{n-2}+2\beta^{n-2}$$

[sterile pumice]

Simple_Art:

[vast vessel]

make sense?

[dense pecan]

yeah

[vast vessel]

okay, so you see what you can cancel?

[dense pecan]

but can you random beta?

oh nvm

[vast vessel]

assume beta doesn't equal 0

otherwise you're dividing by 0

[dense pecan]

$\beta^{n-2$

[sterile pumice]

qwerty.:
Compile Error! Click the reaction for details. (You may edit your message)

[vast vessel]

Okay, so what does the equation become?

[dense pecan]

$$\beta^2 = 3\beta \cdot +2$$

[vast vessel]

[sterile pumice]

qwerty.:
Compile Error! Click the reaction for details. (You may edit your message)

[vast vessel]

Uh wut

[dense pecan]

wait

its +

3 beta + 2

[vast vessel]

$\beta^2=3\beta+2$

[sterile pumice]

Simple_Art:

[vast vessel]

This what you meant to type?

[dense pecan]

yeah

[vast vessel]

k

So what're the solutions for beta?

(They won't be nice)

[dense pecan]

.

[vast vessel]

No

Just move eveything to the left side and use the quadratic formulae

[dense pecan]

beta^2 - 3beta -2

.

[vast vessel]

...

Just use the quadratic formulae

[dense pecan]

2,3

[vast vessel]

2^2 = 4
3*2+2 = 8

I already told you

It's not gonna be nice

Just use the quadratic formulae

$$\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

[sterile pumice]

Simple_Art:

[dense pecan]

$(3+ \sqrt17) \over 2$

[sterile pumice]

qwerty.:

[vast vessel]

$$\beta=\frac{3\pm\sqrt{17}}2$$

[sterile pumice]

Simple_Art:

[vast vessel]

so these are our possible beta

So we conclude our first lemma:

Every exponential function satisfying the equation is given by \$\alpha\cdot\left(\frac{3\pm\sqrt{17}}2\right)^n$

[sterile pumice]

Simple_Art:

[vast vessel]

for some alpha

The second step is to show that when we have:

$$a_n=\alpha_1\cdot\left(\frac{3+\sqrt{17}}2\right)^n$$ $$b_n=\alpha_2\cdot\left(\frac{3-\sqrt{17}}2\right)^n$$ $$c_n=a_n+b_n$$

[sterile pumice]

Simple_Art:

[vast vessel]

then c_n satisfies the equation

This is pretty easy to do:

$c_n$\$=a_n+b_n$\$=(3a_{n-1}+a_{n-2})+(3b_{n-1}+b_{n-2})$\$=3(a_{n-1}+b_{n-1})+2(a_{n-2}+b_{n-2})$\$=3c_{n-1}+2c_{n-2}$

[sterile pumice]

Simple_Art:

[vast vessel]

since a_n and b_n satisfy our original equation

[dense pecan]

oh third line will have 2(B_(n-1) + B_(n-2))?

[vast vessel]

hm?

I put in the definition of c for the first => second lines

I used the fact that a and b satisfy the original equation for the second => third lines

[dense pecan]

oh i see

[vast vessel]

then I regrouped

and used definition of c

More generally it's saying if you find 2 solutions to the recursive equation

and then add them together

you get another solution

[dense pecan]

yeah

[vast vessel]

Okay, so now we have this:

$$c_n=\alpha_1\cdot\left(\frac{3+\sqrt{17}}2\right)^n+\alpha_2\cdot\left(\frac{3-\sqrt{17}}2\right)^n$$

[sterile pumice]

Simple_Art:

[vast vessel]

this ^ satisfies our equation

so as long as we find alphas where c_0 = 1 and c_1 = 2

then we found the solution to your equation

So plugging it in

what do you get for c_0?

(Hint: x^0 = 1 for all non-zero x)

[dense pecan]

a1 + a2

$\alpha1 + \alpha2$

[sterile pumice]

qwerty.:

[vast vessel]

$$1=\alpha_1+\alpha_2$$

[sterile pumice]

Simple_Art:

[vast vessel]

Similarly,

[dense pecan]

yeah

[vast vessel]

$$2=\alpha_1\cdot\left(\frac{3+\sqrt{17}}2\right)+\alpha_2\cdot\left(\frac{3-\sqrt{17}}2\right)$$

[sterile pumice]

Simple_Art:

[vast vessel]

🤢

so uh

if you solve these equations

you have your answer for the exact formulae

[dense pecan]

yeah

[vast vessel]

I'll solve by eliminating alpha_2

$$\alpha_2=1-\alpha_1$$

[sterile pumice]

Simple_Art:

[vast vessel]

$$2=\alpha_1\cdot\left(\frac{3+\sqrt{17}}2\right)+(1-\alpha_1)\cdot\left(\frac{3-\sqrt{17}}2\right)$$

[sterile pumice]

Simple_Art:

[vast vessel]

If you simplified this you would get:

$$2=\sqrt{17}\alpha_1+\frac{3-\sqrt{17}}2$$

[sterile pumice]

Simple_Art:

[vast vessel]

$$\sqrt{17}\alpha_1=\frac{\sqrt{17}-1}2$$

wait no

[sterile pumice]

Simple_Art:

[vast vessel]

$$\alpha_1=\frac{17-\sqrt{17}}{34}$$

🤢 this is what you end up with

no wait

[sterile pumice]

Simple_Art:

[vast vessel]

$$\alpha_2=1-\alpha_1$$

[sterile pumice]

Simple_Art:

[vast vessel]

$$\alpha_2=\frac{17+\sqrt{17}}{34}$$

[sterile pumice]

Simple_Art:

[vast vessel]

$$X_n=\left(\frac{17-\sqrt{17}}{34}\right)\cdot\left(\frac{3+\sqrt{17}}2\right)^n+\left(\frac{17+\sqrt{17}}{34}\right)\cdot\left(\frac{3-\sqrt{17}}2\right)^n$$

[sterile pumice]

Simple_Art:

[vast vessel]

And thus that is your exact formulae

== (3-sqrt(17))/2

[stoic basin]

-sqrt(17)/2 + 3/2 = -0.56155281280883

[vast vessel]

Since this is between -1 and +1, the second part approaches 0

so the best exponential approximation for your sequence is given by:

$$X_n\approx\left(\frac{17-\sqrt{17}}{34}\right)\cdot\left(\frac{3+\sqrt{17}}2\right)^n$$

[sterile pumice]

Simple_Art:

[dense pecan]

yeah got it thanks

[vast vessel]

[dense pecan]

[prisma helm]

Could I get an explanation on mathematical induction?

[naive temple]

you have a set of statements

each statement is given a natural number

1,2,3 and so on

you prove that if statement number n is true, then statement n+1 is also true

then you prove that statement 1 is true

and thats enough to prove that all statements were true

for example you want to prove that the sum of all the n first positive integers is n(n+1)/2

if it is true for n, then for n+1 it must be (n+1)(n+2)/2

but that's exactly n(n+1)/2 + n+1

so that shows that if it's true for one case, it's true for the next case

then it's easy to see that it is true for n=1

and that is it

[valid lodge]

Also, induction might seem pretty intuitive once you understand it, but it actually only works because it's an axiom (search Peano Axioms) - you can't show that induction works from the other axioms

[bitter yew]

did you know peano kinda stole them from dedekind?

[wild zinc]

is that all induction or just non-finite induction?

[bitter yew]

all

[wild zinc]

ya just searched

it seems like there should be some way to define the naturals in such a way that you don't need an axiom but I guess when you try to actually put one together it breaks down in some way

[bitter yew]

axioms are axioms because they cant be proven out of stuff we have already

[wild zinc]

well induction calls on the ability to reach all natural numbers by repeatedly using the successor function from some starting point

if you instead defined the naturals to be the set {0, S(0), S(S(0)), ... } then I can't see why you'd need an axiom for induction

because you have the necessary property by definition

of course it's quite possible that some other property we want of the naturals breaks down when you define them that way

[bitter yew]

okey i will correct myself

they are called axioms but they can and are actually a single theorem that can be proven from set theory axioms

but because they allow u to contruct natural numbers just by itself, they are bundled as axioms

[slow aurora]

Yo

[naive temple]

axioms that can be proven?

[slow aurora]

Sorry yo interrupt

[naive temple]

that's weird

[slow aurora]

But somebody just found the 51 mersenne prime!!!!

[bitter yew]

they are not real axioms

relative to set theory

but if u take peano's arithemtics, they are axioms of that system

[naive temple]

hmmm

where did he found the prime

[bitter yew]

GIMPS

some weeks ago

confirmed yesterday

[naive temple]

finally

I don't get it tho

did they already know it

and just computed it

or what?

[bitter yew]

i guess they checked it already

it was found some weeks ago as i said

[vast vessel]

@wild zinc ya, PA has two different formulations of induction. Either "any set containing 0 and closed under successors contains all naturals" (i.e. your statement) or the more standard one where P(n) => P(n+1)

[wild zinc]

ya ok makes sense

[bitter yew]

also you have to remember induction is not 5th axiom, just principle of it is 5th

actual induction is proven out of it

[valid lodge]

Well that depends on how you define "induction"

[bitter yew]

ye kinda

but assuming everyone menas induction as if property holds for k then it holds for k+1 is a theorem nto axiom

[valid lodge]

Well I mean

That's sort of the same as the axiom just a little casually done and with a shift in the base case XD

[bitter yew]

but axiom was used to prove the theorem, so its not an axiom

[valid lodge]

Huh?

What's the theorem you're talking about

[bitter yew]

mathematical induction

[valid lodge]

Yeah and what does it state

Like most people just say OK base case: it works for b so done. Assume it works for k > b, then we've proven that it works for k+1 so that's done too, so it's true for all k > b

But that's the same as saying "let P(n) be the proposition that it works for n - b"

[bitter yew]

this in short

[valid lodge]

Let S be the set containing all n for which P(n) is true

[bitter yew]

is the theorem

[valid lodge]

How is that different to the axiom except that it lacks the set construction

[bitter yew]

well it is different because axioms talks about numbers belonging to a set and set equaling N

and never about predicates propositions and "functions", but that i mean P(n)

[valid lodge]

Well I mean

They are pretty much isomorphic

I wouldn't call casual induction a "theorem"

Unless you learnt that somewhere?

[bitter yew]

well, maybe u dont call it a theorem, but its a statement that is proven by axioms, while its not being an axiom itself

at uni they showed us, i guess one of the proofs, or only one idk, by constructing a set and showing its inductive

[valid lodge]

Oh hmm

Well idk

It seems to me that the way we normally do induction is just the same as the axiom, just treated in a more casual way

We usually skip the construction of the set and we can start at an arbitrary number for our base case (instead of 0) but everything else seems to be the same?

[crimson ibex]

Has there been any recent developments to the Collatz conjecture?

[valid lodge]

I'm not up to date with current research, but I am very interested in the conjecture myself

Like, interested as in I've probably spent 30 hours on it lol which isn't much

But I haven't really spent any time on any other open problems at all (apart from chromatic number of the plane)

[abstract sinew]

@crimson ibex I don't think so. Searching the arXiv for "collatz" doesn't give anything with much promise (https://arxiv.org/search/?query=collatz&searchtype=all&source=header)

[wild zinc]

that brings up some god-awful papers

how do they get accepted

[crimson ibex]

Arxiv is a preprint server so they have not been accepted in any journals yet

People just put them up there because the process to make it through a journal review committee can take anywhere from a few months to a year

[abstract sinew]

You still need some kind of credentials to get it on the arXiv though

Like, random people can't post to the arXiv, I believe that you need to get "vouched for" by someone who is already on the arXiv

[naive temple]

if p <b and p and b are coprimes

is p² = 1 mod b?

[stuck lintel]

no

[naive temple]

hmm

I'm looking at the group formed by all the integers that are coprime to 12 under multiplication modulo 12

and there's this line of 1s down the diagonal. why?

[naive temple]

Hmmm nice

[sturdy dirge]

Cayley table ?

[stuck lintel]

the 1's mean that the numbers in the column and row are multiplicative inverses

also hi quantic!

[naive temple]

but why is each number its own inverse in this case

maybe because they are all primes?

(1,5,7,11)

[sturdy dirge]

Hello Plum.

[stuck lintel]

😊

[dry oak]

@naive temple because 12 has a lot of divisors

[naive temple]

I can see that

but I don't get why that is related to each number being its own inverse

[dry oak]

1,5,7,11 are all cong to 1 modulo some divisor of 12

you can probably consider this a coincidence

it doesn't hold in general

[naive temple]

😢

checked for 20

I get just some 1s but some 9s too

I guess it's just a coincidence

[wild zinc]

all primes >= 5 are 1 mod 24

[brittle patrol]

you mean all primes squared ?

[lusty cobalt]

Wait what Mudkip?

[wild zinc]

ya ofc woops

[lusty cobalt]

lol

[wild zinc]

I guess I forgot to include it because of the context

[brittle patrol]

A man from Discord disproved Dirichlet's Theorem in one quick step. Mathematicians hate him!

[wild zinc]

:^)

[subtle flare]

legendary isn't just for show

[dry oak]

do I smell inconsistency of arithmetic

[wild zinc]

I shouldn't do maths when I'm tired apparently :^)

[past summit]

Don't drink and maths either

[subtle flare]

someday I wanna be the top dog of maths, then just drink and maths, put out the wackest paper which people will actually try to take seriously

[upbeat wren]

@naive temple Every number coprime to 12 must be of the form: 12x + 1, 12x + 5, 12x + 7 , and 12x + 11.

Squaring each expression gives ...
(144x^2 + 24x + 1) or (12A + 1)
(144x^2 + 120x + 24 + 1) or (12B + 1)
(144x^2 + 168x + 48 + 1) or (12C + 1)
(144x^2 + 264x + 120 + 1) or (12D + 1 )

for some integer A, B, C, and D. Thus, the residues you are dealing with 1, 5, 7, 11 all have squares equal to 1.

@subtle flare you are kinda too late. Read this story (https://pdos.csail.mit.edu/archive/scigen/) about a research paper engine.

[subtle flare]

big rip

[unkempt hedge]

How would you solve a relationship between a and b here:
81a == 0 (mod 2a+b)

[sturdy dirge]

$\exists k\in\mathbb{Z}, (2a+b)k=81a$.

[upbeat wren]

a | bk

[unkempt hedge]

I want to find out how many solutions (a,b) if 1 <= a <= 9 and 0<=b<=9

[sturdy dirge]

Count (write a program if needed).

[sacred junco]

Why does division in modular arithmetic not work the same as multiplication?

[past summit]

Could you be more specific. I mean you don't really have division but modular inverses but modular inverses don't exist for every element.

Unless it's modulo a prime number where inverses exist for all Nonzero elements

[white bear]

Does anyone have a proof of the sum of the digits of any prime cubed is a multiple of 3 away from the prime

(I can also ask in advanced number theory, I’m not sure how complex the proof is)

[sterile pumice]

EpicGuy4227:

[inner crest]

@white bear

[white bear]

Thanks

[upbeat wren]

f(n) = n (for all whole numbers)

d(q, n) = n (if q divides n)
d(q, n) = 0 (if q does not divide n)

For all primes p:

g(n) = f(n) - d(2, n) - d(3, n) - d(5, n) ... - d(p, n) ...

What is the first n > 1021 such that g(n) = 0?

What is the first n > 0 such that g(n) = -kn for k = 2, 3, 4, 5?

[lunar quiver]

Prime number sieve

[upbeat wren]

hmm @lunar quiver how do you guarantee enough primes to get from sieve N to N+1?

Like there is a nonprime in the second term of the line ...

p1 ×p2 ×p3 ×m+19=19,49,79,109,139,169,199

How do you know that by continuing your pattern there will not be all composites in the second term of every p1 x p2 x p3 ... pn x m + "old p"?

[noble jay]

@upbeat wren if n is strictly greater than 1021 then the first number is 1031

since 1021 and 1031 are both prime they both verify the equation

all primes above 1021 verify g(n) =0

[upbeat wren]

I must disagree. :). The first question is the trickiest.

[noble jay]

why is that

[upbeat wren]

hmm try the calculation for it for some low numbers. 😃

[noble jay]

g(n) =0 implies n = the sum of d(p,n) where p is a prime that divides n

since the other sum is equal to 0

since d(p,n) =n then n = sum of n

which is only possible if p =n

[upbeat wren]

um what is g(4)?

[noble jay]

4 - 2 =2

the question is for primes p

[upbeat wren]

4 - 4?

[noble jay]

oh right 4-4

[upbeat wren]

😉

[noble jay]

then how would you do it

[upbeat wren]

hmm what is g(8)?

g(81)?

[noble jay]

they all only have one prime divisor

[upbeat wren]

yup 😃 back to 1022 again!

[noble jay]

1022 has 3

[upbeat wren]

yar so not that one. Keep going 😃

[noble jay]

1024

[upbeat wren]

ding ding ding ding ding ding

Gratz 😃

[noble jay]

but still

the solution is every number with only one prime divisor

[upbeat wren]

yes, but the least one above 1021

[noble jay]

so all prime numbers are solutions

ok

[upbeat wren]

I agree. All primes, p, make g(p) = 0

But others do too

[shut schooner]

How can i determine if two quadratic forms are equivalent (over the integers)?

As in, is there some sort of algorithm?

actually maybe this should go in advanced number theory?

[swift shard]

Some people here may know. I personally don't. What's a quadratic form? Lol

[shut schooner]

A quadratic form is just a polynomial (possibly in many variables) of degree 2

[swift shard]

Sounds like algebraic geometry?

[shut schooner]

Two quadratic forms are equivalent if there is some invertible change of variables (in the integers) such that you can get from one form to another

in particular, this means that they represent the same numbers

[swift shard]

Ahh gotcha

Thx for the crash course. I can try to look it up lol

[shut schooner]

its kind of similar to change of basis

but not really sure lol

[abstract sinew]

a great source for these kinds of things is the first chapter of cox's "primes of the form x^2 + ny^2"

[shut schooner]

ok ill take a look

ok yea it has some good information on what i'm working on, but its not entirely clear to me how we determine that two forms are equivalent

[abstract sinew]

I think that's actually a really hard problem in general

the number of equivalence classes of quadratic forms of a given discriminant is called the class number of that discriminant

and calculating that number is not easy to do

[shut schooner]

agreed, but just a change of variables shouldn't be too hard?

like its similar to completing the square, right

[abstract sinew]

is it? I think it's a bit more subtle than that

I mean, one way to do it is to just try to write out g(px + qy, rx + sy) with p,q,r,s as variables, set it equal to f(x,y), and try to solve for p,q,r,s

by equating coefficients

but those are gonna be nonlinear

which means you're in for a mess

[shut schooner]

oh right

im kinda looking for something with matrices though

i feel like it's something nice

not sure yet

I think its pretty clear that there is some kind of algorithm though, as shown in Bhargava's 290 theorem paper

[abstract sinew]

I mean that is kind of a different method

have you read Serre's "a course in arithmetic"?

[shut schooner]

i haven't

[abstract sinew]

the first half of that book has a lot about quadratic forms over Q

but part of it uses the theory of quadratic forms over the p-adics

[shut schooner]

yea i've been doing some stuff with local representability as well

i think something similar to what i want is found here: https://github.com/sagemath/sage/blob/master/src/sage/quadratic_forms/quadratic_form__equivalence_testing.py

the last function, is_rationally_isometric

but this seems to allow a rational change in variables, not just integral

[abstract sinew]

yeah

so global forms are determined locally

but that might only be true rationally

(I think that's true at least)

(but I could be misremembering. serre would know)

well

[shut schooner]

i think it's pretty close

u just have a finite check

[abstract sinew]

if the change of basis matrix isnt integral then you can detect that locally

cuz some denominator has to have some prime

[shut schooner]

um could you explain?

how do you find the change of basis matrix in the first place?

[abstract sinew]

so I was just suggesting that if it were true that you could detect global equivalence by looking locally at all places

then maybe you could also check integral global equivalence, because if two forms were globally equivalent by some rational change of basis, but not integrally equivalent, then that matrix would necessarily have a denominator

and then that wouldn't be an integral matrix at the primes of the denominator

but that doesn't rule out that there might happen to be another integral change of basis at that place

[empty falcon]

some one teache me an identity quick

[swift shard]

e^(it) = cos(t) + isin(t)

[vast vessel]

kek

[empty falcon]

ok someone teach me an identity with integers

[vast vessel]

$\int_0^\pi\cos^m(x+\ln(\sin^2(nx)))~\mathrm dx$ can be solved when $m$ is even and they are coprime.

[abstract sinew]

wait what

[sterile pumice]

Simple_Art:

[abstract sinew]

is that tru tho

what do you mean "can be solved"

[vast vessel]

Can by written as a rational multiple of pi^k for some integer k

[abstract sinew]

are the other ones provably not a rational multiple of some integer power of pi?

[vast vessel]

idk

[swift shard]

@empty falcon
a^φ(n) ≡ 1 (mod n)

[empty falcon]

what does that even mean

not i have primary and middle school math education + bunch of other stuff - a lot of holes

so i dont really know much notation but i want to know

so please teach me

[sterile pumice]

$a^{\phi(n)}\equiv\pmod{n}$.

[vast vessel]

If $a$ and $n$ are coprime, then $a^{\phi(n)}\equiv1\pmod n$, where $\phi(n)=n\prod_{p|n}\left(1-\frac1p\right)$ for prime $p$.

[sterile pumice]

Simple_Art:

[vast vessel]

@empty falcon

[sacred junco]

How to prove the statement n^4 > n^2 is true

by math. induction?

any natural nubmers

all nautral

n>0

ofc, but can it be proven by math. induction?

Can u show pls?

Thank you

So by looking at expansions you can intuitively say that this is true?

@paper nova

[noble jay]

@sacred junco or you can just do n^4 - n^2 as a difference of squares and use the fact that n is an integer >0 so n>=1

also if you want the strict inequality n has to be strictly greater than 1

[sacred junco]

Thanks

Does anyone have examples which satisfies these conditions in math. indcution?

"The proof by induction needs two steps: 1. base case, 2. induction step.
Both are necessary. Make wrong examples which satisfy only 1 or only 2.
It may be very instructive to construct an example which has a wrong assumption (base case wrong) but which satisfies the induction step."

[swift shard]

All positive integers are 1

Clearly the first integer is 1, so that satisfies the base case

-All positive integers are greater than 1
If an integer is greater than 1, then the next integer is greater than 1, so that satisfies the inductive step

@sacred junco

[sacred junco]

But is it wrong in some where?

[swift shard]

Oh both are very wrong

Clearly not all positive integers are 1

[sacred junco]

Thxx

[upbeat pivot]

Does anyone have any intuitive explanation as to what a well-ordered set is?

What I understand is that if you have a set, say S, then it is well ordered if every nonempty subset of S has at least one element

[modern oxide]

has a least element

More precisely, in order to give a well ordering on $S$ you have to give two things.

1. A total order on $S$.
2. Show that given any subset $R\subseteq S$ there exists an element $r\in R$ such that for all $x\in R$, $r\leq x$ with regards to the total order from (1).

[sterile pumice]

mudkipz:

[modern oxide]

@upbeat pivot

[valid lodge]

@sacred junco oh lol you're here too XD

hi 😄

btw you can drop the "math." before induction

[sacred junco]

no

[valid lodge]

wew

there's no point though XD

nobody calls it "mathematical induction"

Also how far are you in your IA?

Because if you aren't that far then one thing I really really think you should do is prove that addition and multiplication are commutative, associatve, and distributive starting from Peano's axioms

It's actually soooooo helpful

Hang on, let me get something for you:

@sacred junco

Hang on did that send?

Ah there we go

[sacred junco]

Quite far, im just exploring it by stating the basic rules, therweby discussing its significance and application

Thanks, ill have a small look

[valid lodge]

Ah

well the "basic rules" are actually axioms

[sacred junco]

of Peano?

[valid lodge]

Yeah

It's called the "axiom of induction"

[upbeat pivot]

@modern oxide thank you that makes sense

[valid lodge]

Oh, Peano Axioms also contain 4 other axioms which deal with the naturals directly - just search up the wikipedia article on it - the handout I sent is a sheet for defining addition/multiplication and proving properties about them via induction, not really for an introduction to peano arithmetic

[sacred junco]

ill check

[valid lodge]

just when you finally understood induction as being "intuitive", you realise that it doesn't even have to be true, and it only is because we've defined it to be true XD

[upbeat wren]

Hmm I find atheist arguments are like cheap Fermat's Last Theorem proofs. I don't disagree with the theorem, but the proof usually has a lot of holes in it.

[balmy falcon]

okkkkk

[tranquil warren]

anyone?

[compact beacon]

Try expanding (x+1)^n with binomial theorem maybe

[noble jay]

@tranquil warren by taking mod x and mod x+1 we get 2002=0 mod x
and 2001 = (-1)^n+1 mod x+1
if n is odd then n+1 is even and x+1 divides 2000
by considering the divisors of 2000 and 2002 you can check the cases manually we find x=7
if n is odd and x=7 then modulo 3 we have
7^n+1 - 8^n = 0 mod 3
1 - 2^n = 0 mod 3 or 2^(2k+1) = 1 mod 3 which is false
so x cannot equal 7
so n is even and x and x+1 divide 2002= 2x7x11x13 = 14x13x11
so clearly x=13
so the equation becomes
13^n+1 - 14^n = 2001
since n is even then
13^2k+1 - 14^k = 2001
mod 8
5 - 4^k = 1 mod 8 or 4^k = 4 mod 8
now if k>2 then 4 =0 mod 8 which is impossible and k!=2 so k=1
so finally x=13 and n=2
13^3 - 14^2 =2001 is the only solution

[tranquil warren]

https://tenor.com/view/full-house-kiss-kisses-gif-4408898

thanks bud

[noble jay]

np

that was a nice problem
let me know if you need more help

[stuck lintel]

dusty op number theory god

[noble jay]

@tranquil warren i made a little mistake it's fixed now

also here's a little program in case you don't feel like checking cases manually

@stuck lintel nah i'm as terrible as the next guy

[sturdy dirge]

Python.

#!/usr/bin/env python

# -*- coding: utf8 -*-

n = 1
for x in range(2, 2003):
    if 2002 % (x + 1) == 0 and 2002 % x == 0:
        print(x)
    else:
        n = 2

if n == 2:
    print("No more solutions")

m = 0
for x in range(2, 2003):
    if 2002 % x == 0 and 2000 % (x + 1) == 0:
        print(x)
    else:
        m = 1

if m == 1:
    print("No more solutions")
```.

[noble jay]

@sturdy dirge Thanks
btw do you know how i can write that in a more efficient way

[sturdy dirge]

Not sure, maybe one loop with:```Python
if 2002 % x and (2002 % (x + 1) or 2000 % (x + 1)):

[noble jay]

it's like two different programs,solutions when x and x+1 divide 2002
and other solutions if x+1 divides 2000

[sturdy dirge]

Then an other solution is to do one loop, store x or a bookean and finally print.

[green vortex]

Hello, I'm writing a program and a part of it needs to do the following task: given a, b, c, x, y are positive integers and the value of a, b, c, determine whether equation ax + by = c has solution(s) and if yes, provide one solution.

Since the numbers are small, it's doable with just brute force trying all possible x values and see if y comes out to be an integer, but I wonder if there is a more computationally efficient method than that.

[past summit]

Look at Euclid's algorithm

[green vortex]

Thanks I'm reading into it.

[green vortex]

I'm not quite getting it, extended Euclid's algorithm solves for the situations (using my variables) which c is the GCD of a and b, but that isn't necessarily the case in my problem.

Sorry math isn't really my strong suite.

[noble jay]

@green vortex by going backwards from the algorithm you can find 2 values for x and y verifying the equation

i'll write down an example

[green vortex]

That would be great!

[noble jay]

i was trying to find a clear example on google but couldn't. rip
anyway say the equation is
9x +32y =5
then
32= 9x3 +5
9=5x1 +4
5 = 4x1 +1
now going backwards
1=5-4
then you plug in values line by line until you only have 1 i terms of 9 and 32
so
1 = 5 - (9-5)
1= 5x(2) -9
1= (2)x(32-9x3) -9
1 = 32(2) -9x6 -9
1 = 32x2 - 9x7

multiply by 5 and your solution is
(x,y)= (10,35)

[green vortex]

How did you go from
9x +32y =5
to
32= 9x3 +5

[past summit]

Euclid's algorithm

First you find the GCD and then 'unzip' it starting from where it terminates

[green vortex]

Okay I think I got it now, thanks a lot for the help everyone!

[woven briar]

hi, i have done part (c) by going to the midpoint of the two rationals and then going to the ever more midpoints between the initial and this midpoint generating infinite rational numbers and i proved it with induction. i am not sure if this is the way i am supposed to do it as it seems a bit long winded, perhaps i can use axioms? part (d) i cannot do with a similar way and I think I have to perhaps use the completeness axiom but i do not know how to do that. help please with part (d)

we have these axioms

[sacred junco]

try making a weighted mean of the two rational numbers, with such weights so that their mean is irrational

[woven briar]

so i could divide their difference by the irrational number, so that the resulting number is irrational and within the range of the first and the second, then add this irrational number to the first so that we obtain an irrational number between the two? i can do the final part of that as this part we proved it

but i would then have to prove that a rational divided by an irrational is irrational

[woven briar]

i did this, it seems a very weird way about it

sorry the third picture comes before the second picture

i think i should say bdϕ is not an integer because ϕ is irrational

[sinful hornet]

Is all of this pretty basic? https://www.youtube.com/playlist?list=PLr3WmPgPWZfX1HUpeyKkP6ir2wOFhqXMO

[swift shard]

No not all of it

That's a lot of videos, lol

[sinful hornet]

yeah, I watched the first 30 or so earlier

not too bad they’re only 2-4 mins generally

I’m assuming the further down u get, the more difficult

[hexed knoll]

$\left(2a-b-3\right)^2+\left(3a+b-7\right)^2=0$
Putting the above equation in WolframAlpha yields the integer solutions 1 and 2.
Is there a method for solving diophantine equations in this form?
Or is WolframAlpha somehow brute forcing the solution?

[sterile pumice]

memes:

[stuck lintel]

since squares are always nonnegative and their sum is 0 then (2a-b-3) = 0 and (3a+b-7)=0

[hexed knoll]

Okay I didn't think about that. Thanks

[hazy hawk]

What's the smallest positive integer that is a product of three prime numbers(not necessarily different), where all numbers created writing those three prime numbers one after another are prime?

[valid lodge]

113, 131, 311 are all prime

so 1x1x3 = 3?

oh wait

nvm lol

[inner crest]

63

@hazy hawk

[hazy hawk]

thanks!

[weary sigil]

So I want to prove that the number composed of $179$ ones in a row is composite. I can express it as $\frac{10^{179}-1}{9}$, but then what? After checking on factordb I can see that it's divisible by 359, which implies $$10^{179} \equiv 1 \pmod{359}.$$ That screams Fermat's Little Theorem, but $\lambda(359) = 358$ since it's a prime, and that's $2 \times 179$. Is there some special condition for taking the square root of both sides of a congruency? And more importantly, how could I have found that factor "organically"?

[sterile pumice]

NieDzejkob:

[stuck lintel]

if you've shown it's divisible by 359 then it's composite....?

[weary sigil]

If plugging the expression into a calculator can be called showing then yeah, but with constant data that's trivial

the goal is to make it checkable by a human, then to learn to solve problems like this without knowing the factor

[gilded tinsel]

wait nvm im an idiot

[stuck lintel]

i mean the modular inverse of 1 in mod 359 is 1, so since 10^358 = 1 mod 359, then 10^179 = 1 mod 359

[weary sigil]

I'm not sure I follow

[stuck lintel]

modular multiplicative inverse?

[weary sigil]

yeah

I know what that is

[sterile pumice]

NieDzejkob:

[gilded tinsel]

the modular inverse is unique

so you can take a “modular square root”

[brittle patrol]

No you can't

There's at least two numbers that squared give you the result

like (-1)^2 is still 1

[gilded tinsel]

oh yeah

im pretty sure its an open problem to determine whether there are infinitely many primes of the form 11...11 tho so thats kinda interesting

[weary sigil]

but it doesn't always work: $9 \equiv 0 \pmod 9 \not \Longrightarrow 3 \equiv 0 \pmod 9$

[sterile pumice]

NieDzejkob:

[brittle patrol]

Yeah exactly, what I said

You can't square root in modular

[weary sigil]

hmm, for a prime $n$ I've got $x^2 \equiv 1 \pmod n \Rightarrow x^2 - 1 \equiv 0 \pmod n \Rightarrow (x + 1)(x - 1) \equiv 0 \pmod n \Rightarrow n \mid (x+1)(x-1) \Rightarrow n \mid (x+1) \lor n \mid (x-1)$, but I'd need $n \mid (x+1) \land n \mid (x-1)$ to prove the above

[sterile pumice]

NieDzejkob:

[weary sigil]

actually you can just replace the $\Rightarrow$s with $\Leftrightarrow$s and it'll still work and that's enough

[sterile pumice]

NieDzejkob:

[sturdy dirge]

Better \iff.

[brittle patrol]

But this isn't true:

$n|(x-1)(x+1) \implies n|x-1 \vee n|x+1$

[sterile pumice]

Gonzo17:

[sturdy dirge]

Counterexample: 15 | 3 * 5 and 15 doesn't divide 3 nor 5.

[noble jay]

@brittle patrol No

if and only if n is prime

[brittle patrol]

Dude

Read my whole message

I was telling him it's not true

[weary sigil]

at the beginning of the message I say I assume n to be prime

[brittle patrol]

Oh okay then

It's a pretty well established result when n is prime

[weary sigil]

which one?

[brittle patrol]

Basically then $x^2-y^2=(x-y)(x+y)$ gives you that for two squares to be equal mod p you need x+y or x-y to be divisible by p

[sterile pumice]

Gonzo17:

[brittle patrol]

Which means we can pair up all the residues modulo p into pairs giving the same residue when squared

into (x, p-x)

except for 0, which would give (0,0)

otherwise for odd p all the other pairs are actual pairs

So we get that presicely half of numbers 1, 2, ... , p-1 are residues of squares

We call them quadratic residues modulo p

And each one is achieved by exactly two squares

Which for example means that if $x^2\equiv 1 $ (mod p) then $x\equiv 1$ or $-1$

[sterile pumice]

Gonzo17:

[brittle patrol]

Some cool stuff

Then you can examine further which residues are quadratic residues

[wooden creek]

hi

how can i prove this?

[weary sigil]

there's nothing to prove

at least, with this much information

[sterile pumice]

NieDzejkob:

[sterile pumice]

NieDzejkob:

[weary sigil]

can you take it from there?

[wooden creek]

im sorry but i cant, can i get another hint?

[sterile pumice]

NieDzejkob:

[wooden creek]

thanks

where can i get documentation about this type of congruences?

[weary sigil]

https://en.wikipedia.org/wiki/Modular_arithmetic#Properties

[wooden creek]

thanks

[weary sigil]

How do I go about proving $$\lnot\exists x, y \in \mathbb{Z} : \frac{x^2 + 1}{y^2 + 1} = 2019$$?

[sterile pumice]

NieDzejkob:

[jolly crypt]

You start by trying to show $$x^2 = 2019y^2-2018 $$ is impossible.

[sterile pumice]

matorin57:

[jolly crypt]

That can be done by trying to show it cant be a square

And we know that x and y must have the same parity

(can be done by doing cases on RHS)

[inner crest]

@weary sigil 2 is not a quadratic residue mod 3.

[lean halo]

for number 102 why is 9^6 - 1 = 888888 base 9

[stuck lintel]

9^6 = 1000000

-1 = 888888

[lean halo]

ok so why is -1 = 888888

[stuck lintel]

oh I meant 1000000 - 1

Think of how I’m base 10 they all become 9’s I.e. 1000000 - 1 = 999999

[lean halo]

that's true for every single base?

[stuck lintel]

yeah 10^n - 1 base b+1 = bbb....b with n b’s

[lean halo]

lol thanks

[stuck lintel]

np

[lean halo]

lol i did this the hard way at first

and wasted like 20 minutes ugh

[lean halo]

Can someone plz explain the very last line to me over divisibility. The "However..." to the end portion keeps confusing me no matter how many times I read it

I feel like if I don't understand divisibility thoroughly it'll leave a gaping hole in my nt knowledge lol

[noble jay]

@lean halo the notation is a bit confusing yeah but anyway
since a1 | a and a1|b then a1| gcd(a,b) (as a result of bezouts identity)
so gcd(a,b) / a1 = an integer we'll call d.
so gcd(a,b) = dxa1
(try to avoid writing divisions in nt but i'll do it here just to make it clearer)
dividing both sides with b and inversing
b /gcd(a,b) = b/(d x a1)
so (b x d) /gcd(a,b) = b/a1
hence b/gcd divides b/a1

again please avoid writing like this in number theory. it's literally cancer imo

[lean halo]

lol what's bezouts identity

@noble jay

Is it one of those foundation things you must know for this subject that books assume you already know

like vieta's formulas to understand newton's sums, etc.

[noble jay]

not really but you can say it's of the fundamentals of nt
so if d =gcd(a,b) then there's a pair (x,y) such that d = ax + by

the proof is not very intuitive the first time but the method is very handy

[lean halo]

@noble jay for bezouts formula could you try plugging in numbers

i tried but now i'm even more confused

if d = gcd(a, b) then try 8 = gcd(56, 40)

so for int x and y, d = ax + by

so 8 = 56x + 40y ??????

oh so x and y are some obscure integers i don't have to worry about?

something something euclidean algorithm

[stuck lintel]

Yeah it’s something called a linear Diophantine equation

If you let x = ag and y=bg where g = gcd(a,b), then you can find a solution to ax + by = z/g using the Euclidean algorithm to find x1 and y1 where ax1 + by1 = 1, then parametrize

[lean halo]

so do i have to understand diophantine equations before I can understand bezouts identity and thus divisibility

dammit I know the statement of bezout's identity

but i can't draw the line as to why a1 | gcd(a, b) given d = gcd(a, b)

and a1 divides both a and b

@stuck lintel

I just want to settle for a more basic understanding for now and cover diophantine equations lateerrrrrr

lol the rest of this chapter looks easy but this one line is what's preventing me from progressing to the end of this chapter

[stuck lintel]

Since a1 | a and a1 | b, let a=x(a1) and b=y(a1), then d = gcd(x(a1), y(a1)) = a1*gcd(x,y) -> a1 | d

you can factor stuff out of gcd btw

Or intuitively, think of the prime factorization of a and b. If some number divides both of their prime factorizations, then they must divide the lowest powers of each of the primes aka its gcd

[lean halo]

ok so i have to comments

for the first thing you said

bc a1 * gcd(x, y) = d that means a1 | d

[stuck lintel]

yeah

[lean halo]

also for the second thing

can i imagine like an irregular terrain with hills or something

and you're slicing off the one slice downwards by which everything is on equal level

[stuck lintel]

Basically

[lean halo]

Hmmmmmmm ok that makes more sense thanksss

[stuck lintel]

👍🏻

[proven topaz]

plum op

[stuck lintel]

kermie omega op

[lean halo]

@stuck lintel could you please help me understand Fermat's little theorem

also is it true it's often used in conjunction with the Chinese remainder theorem so now would be the ideal time to learn it as well

I don't get the part where it says "none of the new numbers ka is divisible by p, so all are congruent to some number in the set"

and thus essentially until the end of that paragraph

lol

[stuck lintel]

just look into Euler's modular theorem

[lean halo]

how is it connected to this

dammit why am i learning so many theorems today lol

Fermat's little theorem, Euler's modular theorem, Chinese remainder theorem, wilson's theorem

I feel so coooooool XD

[stuck lintel]

euler's theorem is a generalized fermats little theorem

idek what wilsons theorem is lmao

[lean halo]

is now a good time to learn the crt

I've been wanting to learn it so badly for sooo long

[stuck lintel]

i guess

CRT is pretty advanced tho 🤔

[lean halo]

wait till the end of the chapter then???

[stuck lintel]

uhhhhhhhhhhh

[lean halo]

lol I'm going from 0 to 1000 in my nt knowledge in two days

[stuck lintel]

i mean you can learn it rn if you want, just might be hard to grapple

[lean halo]

I'l tryyyyyyy

what knowledge does it require then

that i may not understand rn

[stuck lintel]

do you understand all the basics of mod arithmetic?

[lean halo]

ya

it's ez

[stuck lintel]

how do you solve something like this then

find the smallest value of x such that 3^x = 1 mod 143^2

[lean halo]

ok yeah i haven't gotten that far yet lol

[stuck lintel]

you can do it with the basics, just need to think hard about it

[lean halo]

gimmie a sec then

[stuck lintel]

lol is this a good time to include the fact that this was a #11 on aime

or #10 cant remember tbh

[lean halo]

@stuck lintel is euler's modular theorem and his totient theorem the same thing

[stuck lintel]

yh

[lean halo]

@stuck lintel besides all of the theorems in this chapter is there anything else I should consider learning so I don't run into intermediate level problems completely beyond what ik

I'm going to do number theory problems during school tomorrow so i was just wondering just in case

I mean when i'm done i'll have covered divisibility, linear and quadratic congruences, number and sum of divisors, fermat's little theorem, euler's totient theorem, and wilson's theorem so

i might try and give up on crt but is that enough to solve like 95% of nt problems at least

on an intermediate lvl

[odd nexus]

I don’t think any of the review questions in that chapter uses Wilson

and is CRT Chinese remainder theorem?

it doesn’t seem that hard to learn but it’s not all that useful (I’ve only ever used it for working mod stuff and proving stuff about sequences)

[lean halo]

hm

ok so i should focus like 10x more on fermat and euler?

[odd nexus]

idk sorry since I don’t know much about American contests

[lean halo]

ok ok so what is most common in general

[odd nexus]

idk but I’d be less focused on learning theorems and more on doing problems + building intuition

so like

I’d just go through the chapter and try all the review problems

[lean halo]

I''m almost theeeeerrrreeeeee

i just have totient theorem then briefly wilson's then it's problems all the way from theeeerre