elementary-number-theory

[fossil sapphire]

Essentially yes

[unkempt hedge]

But how would I prove this? (calculate this)

mhm

[fossil sapphire]

In the context on our Venn diagram,what does c divides ab mean?

Ok that was a bit vague

For c to divide ab, that means that all factors of c are either in common with a, b or both yes?

[unkempt hedge]

yes

If c was prime it would be either a or b

[fossil sapphire]

So now we have d, a number where all the factors that c has in common with a are also in common with d right?

[unkempt hedge]

yes

[fossil sapphire]

So this means all of the factors of c are in common with either d,b or both right?

[unkempt hedge]

ok

[fossil sapphire]

So what does that imply?

[unkempt hedge]

since d and/or b have common factors with c that means that c divides db, right?

[fossil sapphire]

Yes

So that's essentially the proof

[unkempt hedge]

Well, I understand it in words, but not how you would show it mathematically

[fossil sapphire]

Wdym "mathematically"?

[unkempt hedge]

How you would write down the calculation?

[fossil sapphire]

Maths proofs aren't always just long sets of equations

[unkempt hedge]

So the only way to understand this is through logic?

or intuition

[fossil sapphire]

That proof above would likely be fine as long as you write it clearly and precisely along with the appropriate mathematical statements

[unkempt hedge]

Ok

I have another question/problem, if you don't mind helping me some more?

[fossil sapphire]

Sure

[unkempt hedge]

If x^2+ax+b=0 has an integer root, show that it divides b.

What I think you need to do is prove that b divides (a+root(a^2-4b))/(2) or (a-root(a^2-4b))/(2)

[fossil sapphire]

By "it" do mean x?

[unkempt hedge]

it means if x^2+ax+b=(x-x0)(x-x1) that b divides x0 or b divides x1

I think they mean that b divides one of the roots in the polynomial

[fossil sapphire]

Are you sure they don't mean the roots divide b?

[unkempt hedge]

oh, you are probably right

[fossil sapphire]

In which case try finding b in terms of x1 and x0

[fossil sapphire]

Too complicated

Think simpler

You basically had it when you factorised

[unkempt hedge]

hmmm

[fossil sapphire]

No just x1|b or x0|b

How would you show that?

[unkempt hedge]

the only way I see is

[fossil sapphire]

Still too complicated

[unkempt hedge]

I guess you could join them x1 * x0 = b^2

[unkempt hedge]

b = x0 * x1 , because x^2+ax+b = x^2 - (x0+x1)x + x1 * x0

So x0 and x1 are factors in b therefore both roots divide b ?

[fossil sapphire]

Only if both are integers

Otherwise divides doesn't really make sense

[unkempt hedge]

yes, but this only says if one of them is an integer

[fossil sapphire]

Is b an integer?

[unkempt hedge]

x^2+ax+b = x^2 - (x0+x1)x + x1 * x0 btw, I found this really cool

[fossil sapphire]

O assume it must be

[unkempt hedge]

not sure, but I guess

[fossil sapphire]

Then yes

That's more or less it I think

[noble jay]

@unkempt hedge bezout identity

literally 2 lines

[sacred junco]

how do i find the number of elements of order 9 in the direct product z3 x z9?

[hearty timber]

if (a,0) has order m and (0,b) has order n, what's the order of (a,b)?

think of that

[oak mica]

idc if this is number theory, i just want to ask a quesiton. When you want to derive the roots of a quadratic, and one of the rots is irrational, then you know the other root MUST be irrational. For instance, x^2-3=0, roots are irrational. However, in the equation x^3-3=0, there are two imaginary solutions, leaving only one irrational solution.

My Question: I thought when irrational roots are solutions, that they always come in pairs, as in quadratics. Why is this not true for cubic equations?

[hearty timber]

they don't come in pairs in quadratics either, in fact
consider x^2 - sqrt(2)x = 0

but your general intuition that the roots have to be independent of the rationals if the polynomial is irreducible is correct. the three solutions in x^3-3=0 are irrational in this sense

in fact if you let the real cube root of 3 be z, then the solutions are {z, w z, w^2 z} where w is a cube root of one

[oak mica]

damn son

[sacred junco]

Jacobian is smart as FUCK

[fossil sapphire]

who's FUCK

[fossil sapphire]

do you guys know anywhere which gives a reasonably good/intuitive proof of quadratic reciprocity?

[royal zodiac]

"Intuitive" can mean different things for different people but there's some articles online by UGA on that theorem. Stuff that will be useful for that is Galois Theory so you should study also on that

[fossil sapphire]

yes intuitive can mean different things for different people but given the fact that a person is asking for a proof of it would generally indicate an entry level proof of the theorem.

Personally, I would've thought that was intuitive

but I guess intuitive does mean different things for different people

¯_(ツ)_/¯

[carmine pulsar]

Hey math trivia q to solve in IQ tests

what is the approach(how) to find the last digits of such operations: (73^543)
99^1399

[molten bolt]

if you only need the last digit, in say 73^543

the last digit of 73 will determine last digit of 73^543

So, observing the exponents of 3;

3, 9, 27, 81, 243, ...

It follows a pattern in unit digit; 3,9,7,1 and repeats

So, based on the exponent, here 543, you can figure which one of those four will be the unit digit.

[noble jay]

@molten bolt not necessarily. and theres also a much more efficient way to do this. @carmine pulsar depending on how many last digits you wanna find, you choose either mod 10 if 1, mod 100 if you need 2 ... and so on.
lets assume you're looking for one last digit
so 73=3 mod 10 (now to get to 543, youre going to need to find a value for x such that 73^x = 1 mod 10, now we know that totient 10 is 4 so 73^4,
(the reason we want 1 is because when you multiply exponents you need the smallest number possible after the operation so that you can make the calculations easier)
now that we have 73^4 =1 mod 10
and we know that 543 = 4 x 135 + 3
we can then do
73^(4x135)+3= 1 ^135 x 73^3 mod 10
so that gives us
73^(543) = 73^3 = 3^3 mod 10
73^(543)=27=7 mod 10
so 7 is your last digit

[molten bolt]

oh ok

[noble jay]

its usually just 3 lines lol i just wrote this much to explain properly

[carmine pulsar]

Thanks my leige

[nocturne heath]

@king_wili_math_nerd#3847 for instance if you want the two last digits of 991399, you go modulo 100, and it becomes -1-1=1, so the two last digits are 01.

[tribal halo]

hi guys, can anyone explain what is congruent modulo please?

[sacred junco]

if some x is congruent to y mod m then x= mt + y where t is an integer

@graiser#8627

and he left the server >_>

[vast vessel]

<_<

[somber rampart]

If some x is congruent to y mod m then the natural map Z -> Z/mZ sends x and y to the same point

[half fable]

why inclusion

[somber rampart]

because I'm tired and exhausted from AP exams

[hearty timber]

:(

[stoic basin]

Rendering failed. Check your code. You can edit your existing message if needed.

[hollow basalt]

The last thing is not a statement, it is a set.

[zinc rain]

your statement doesnt make any sense

it isnt even a statement lol

[hollow basalt]

And you never introduced A

But if your assumption is true on the LHS, then what you can say is that B=C.

oh sorry

this is different

they are both intersections in the handwritten photo you sent earlier

[zinc rain]

i mean the condition is just one of demorgan's laws

[hollow basalt]

The LHS of this statement you have texed is always true

[zinc rain]

^

[hollow basalt]

yeah

[zinc rain]

a universallly true statement isnt really an interesting condition

[hollow basalt]

his condition in the handwritten version had both of those things being intersections, which would then imply B=C, but idk what he was trying to get at with his conclusion.

[pine fiber]

its supposed to be $$A\ (B \cap C)$$

[pine fiber]

ug

the fill in is \

[naive sparrow]

Hi

I have a question , could there exist an algorithm that can produce the ℙ of prime numbers , by checking a constant formula , (or checking a certain criteria) .

I think I should make my question clearer , I'm asking if it is proven and certain that such a formula cannot exists that will apply for all of ℙ so that no outlyers enter the group or be filtered out falsly .

[ebon frigate]

I'm still not sure what you're asking. There are algorithms for deciding if a number is prime.

[somber rampart]

yeah there are algorithms which will determine exactly whether a number is prime

they're just very slow

WDYM by "constant formula" though

Because that could throw out some things

[naive sparrow]

Right , I didn't want to use computer termenolidgy in a Math discord server , I'm asking for one in O(1) Time complexity .

[somber rampart]

like there's no algebraic formula to determine it

Yeah nothing O(1)

[naive sparrow]

basicly only plugging certain variables accordingly .

[somber rampart]

Well

[ebon frigate]

There are no algorithms O(1) for deciding if a number is prime.

[somber rampart]

there is an O(1) algorithm for producing prime numbers

[ebon frigate]

But it does not produce all prime numbers.

[somber rampart]

ye

[naive sparrow]

Well I know there isn't one that was found YET , I'm asking if there's a proof for it being impossible .

[somber rampart]

Eh

[naive sparrow]

Because Wikipedia wasn't clear about that .

[somber rampart]

If Riemann Hypothesis were true you could probably get that, I don't think it's been proven though

Riemann Hypothesis lets us know enough about prime distribution (aka that it's essentially random) so you'd have that

Like for example Mill's constant, the one that produces prime numbers (but not all of them), does not have a known value, we just know it exists

but given Riemann hypothesis we have an approximation

[ebon frigate]

It doesn't look like it's -proven- to be polynomial time or worse.

But since nothing is even polynomial time...

It's a strong conjecture.

[noble jay]

can anyone check this?

the little triangle thingy is the french notation for gcd

[somber rampart]

It looks good to me

took me a minute to get the notation but yeah looks good

[nocturne heath]

@noble jay are you French ?

[noble jay]

@nocturne heath yes

i speak french

[sacred junco]

bonjour

[noble jay]

lol sardine

[sacred junco]

[sacred junco]

What are some good resources for learning modular arithmetic

[snow basin]

In my case I used the book: "A First Course in Modular Forms "

[glad nacelle]

@snow basin lol

[mental coyote]

Eva

It should just be intuitibe

i wouldnt bother learning it

just absorb it

[noble jay]

@mental coyote you sure about that

[mental coyote]

im sure about everything

[noble jay]

[bronze breach]

I just had an idea and wrote it down. Is this valid?

[sacred junco]

or you could say since p is a perfect square, it must have some 2^2z as its factor, where z is an integer. therefore, sqrt(p) has 2^z as a factor, and 2sqrt(p) has 2^z+1 as a factor. Since this is odd, it can't be a perfect square

also

=tex p\cdot \sqrt2 \neq \sqrt{2\cdot\sqrt{p}}

oml how do u make that damn does not equal sign

[bronze breach]

\neq

[sacred junco]

ty

[bronze breach]

No problem :)

And my bad, I thought that was true for all positive integers. Isn't it just the reverse of "pulling factors out" of a radical?

Where, say, sqrt(8) is the same as 2sqrt(2)?

[sacred junco]

yes but you're pulling out a square and making it a square root on the outside

=tex \sqrt{x \cdot y^2} = y \cdot \sqrt{x}

[bronze breach]

cough
Of course

[sacred junco]

yea

[bronze breach]

There we go

So then, this would generalize to "there are no perfect squares p where np^2 is also a perfect square and sqrt(n) is irrational," correct?

[sacred junco]

yeah that's correct i believe

[bronze breach]

Cool, thank you

With stuff like this I'm always wary of missing some hidden logical leap, such as an implied divide-by-zero

[sacred junco]

👀

[sacred junco]

is there a pattern behind prime numbers?

[sharp gulch]

Maybe

If you can find it

You'll be recognised as a pretty smart guy

Or if you can prove there is/isn't one

[somber rampart]

@Icchan#2515 yes, they have no factors besides themselves and 1

The challenge is finding a fast pattern with primes

[wild zinc]

I found a function that outputs all the primes

and no non-primes

[sacred junco]

wut

[sacred junco]

._.

[somber rampart]

A+

Implicit formula

[wild zinc]

a non-constructive approach

[silver solar]

truly a breakthrough

[sacred junco]

Not numb theory :p

[silver solar]

Number theory is basically algebra tho

[wild zinc]

lolno

[silver solar]

Ofc there's also analytic number theory but neither of us can deny the large overlap between algebra and number theory

[wild zinc]

I mean yes but not this algebra :^)

[silver solar]

🍮

[upbeat wren]

hey now ... not everyone likes picking the low-hanging fruit of Analytic Number Theory 😃 (jk. I like my mods. You can't take them away)

[glad nacelle]

@trail salmon and @warped sun

So, turns out

Define π(x) to be the number of primes ≤ x

We can define this for all real numbers, mind you

So π(3) = 2, π(π) = 2, π(10) = 4, etc

Theorem

=tex \pi(x) \sim \frac{x}{\ln(x)} \sim \int_e^x \frac{1}{\ln(t)} dt

[trail salmon]

I see.

Most of old mathematicians were interested in prime numbers. What did prime number contribute to the field?

@glad nacelle

[glad nacelle]

So, I'm not well aware of the details on exactly which parts of math came out of which other ones

[warped sun]

Hmm that's actually kinda interesting

[glad nacelle]

Number theory as a whole influenced a whole lot

For example, ring theory

[warped sun]

wait how does that integral work

Hmmm

[glad nacelle]

But I think prime numbers were sort of a primitive thing that people cared about by default which led to a lot of other questions

[warped sun]

It's really late tho so it might be super obvious and I'm just being dumb :l

[glad nacelle]

They also just come up in a lot of places which you wouldn't expect it

For example, the size of a finite field must be a prime power

Groups of prime order are cyclic

Sylow theorems are huge in group theory and they involve a lot about primes

So, the Sylow theorem says that

[warped sun]

waiitt the first one?

is true?

[glad nacelle]

Let's say G is a finite group and $$p^n \mid |G|$$ but $$p^{n+1}\nmid |G|$$. Then you can find a subgroup of $$G$$ of order $$p^n$$ (this is called a Sylow p-subgroup), and you have theorems about the number of such subgroups and their relation to each other which tell you quite a lot. I was able to use Sylow theorems and related things to show that the smallest non-abelian simple group was $$A_5$$

[glad nacelle]

@warped sun yeah it is

[trail salmon]

I see that a way to find a non-commutative group

[warped sun]

I hear research in math tho

is suppperrr boring

You spend your life doing a math problem

and then ten years pass

[trail salmon]

But it worth it.

[warped sun]

lmao

[trail salmon]

I'm not kidding.

It does.

[glad nacelle]

It's the kind of thing where some people find that sort of experience to be enjoyable

[warped sun]

I dunno

for ten years

I think I'd give up after like a month

[idle rapids]

lol

[glad nacelle]

I mean people aren't gonna dedicate fully for 10 years on a single problem

They'll work on others as well

But yeah you do spend a lot of time figuring stuff out. Think about it as a long-term puzzle I guess

[trail salmon]

Yes, indeed.

[glad nacelle]

Definitely not for everyone (tbh I probably need to work on my patience since I'd probably get real frustrated if something isn't clicking for a while, though I've been habituated to psets which are due weekly so maybe I'd be better off trying longer term stuff to see)

[trail salmon]

How old are you, btw. I say it's not a prime number, Haha.

[glad nacelle]

Correct, 20

[idle rapids]

but seriously isn't ten years for mono thing boring..?

[trail salmon]

How old were you when you get into number theory and advanced math?

[warped sun]

wait what sash you're third year

but you're so young

o.O

[glad nacelle]

I'm almost 21 lmao

[warped sun]

Ah

[trail salmon]

Depends on the aspect of said someone personality.
Some scientists dedicated their life for knowledge, they knew what value they did invest their life in.

[glad nacelle]

I'm not that advanced, but I probably started getting serious in college, so let's say I was just turning 18

[warped sun]

what did u do in HS?

[trail salmon]

I see.

[glad nacelle]

And number theory in particular... I had a very brief touch because my math class in high school had everyone do some kind of "independent exploration" and I did mine on modular arithmetic, which I quite liked, but I only started doing stuff, say, summer second year

@warped sun just the usual stuff, aside from having done this "IB" program last two years, which may be slightly different from your usual precalc-calc stuff

[trail salmon]

Were you interested in math since HS?

[warped sun]

aah

[glad nacelle]

Math was always my second favorite thing I'd say

[idle rapids]

what's first lol

[trail salmon]

Physics were your first

[glad nacelle]

Like, it was probably my best subject but at any given time I liked one thing more

[warped sun]

ENglish

bets

[glad nacelle]

When I was a kid my mom sorta tried selling me the idea of being a doctor (it was her childhood dream), which I liked for a while because I thought the human body was cool, but eventually I didn't like it as much anymore

[trail salmon]

Biology I see.

[glad nacelle]

Then I started watching animal planet, for a while I liked astronomy, chemistry, physics, also I was one of those people who obsessed over specs of tech

[idle rapids]

What's your country sash,

[warped sun]

Bets US

Cus he's up at this time :l

[glad nacelle]

There was a point in time where I was interested in econ as well, honestly that's one of those interests that never materialized rather than my having a less than pleasant experience with the subject after a while and dropping it

Yeah I'm in the US

[warped sun]

then why take finance?

It's 2:18 where I am /sigh

[glad nacelle]

Same

[warped sun]

Need to sleep but my laplace is bad

State?

[glad nacelle]

And finance is not ideal but it's one of those things which pays well so if math academia doesn't work out, that's where I'm going

Hmm, maybe I should be vague and say "The Midwest"

Though in general I'm pretty loose about stuff and at some point will probably just say where I am

[trail salmon]

I see, lad.

[warped sun]

Eh I live in Texas

Academia is hard

but math is a bit easier cus it's not expensive :l

Then again I wouldn't be surprised if got less funding

That MD Asian parent dream

/e is strongly pushed for it.

[idle rapids]

I'm from Mo Salah country

[glad nacelle]

Hmm... Is the 7 in your name such that we would possibly write his name as "Sala7"?

[idle rapids]

LOL yes😂

7 = H with more H's

I wonder how you know this tho

[glad nacelle]

I know some Arabic, though depending on where you're from we could probably have some difficulty communicating. Also at this point we're not talking number theory so let's migrate to #chill

[noble jay]

@sacred junco just post in one of the questions channel and ping helpers. you don't have to post everywhere

[foggy kelp]

Is any possible combination of a finite amount of digits findable in any given irrational number?

[half fable]

No

[sacred junco]

Good counter example

0.100111000011111000000...

[foggy kelp]

Okay

Thanks

[warped sun]

Gucci point

[digital kettle]

Any prime of the form 3n+1 is also of the form 6n+1

How do I prove this?

<@&286206848099549185>

Anyone?

Wai5

[noble jay]

huh

[digital kettle]

Done :p

I'm stupid

[wild zinc]

if it's of the form 3n+1 then it's either 3 (2k+1)+1 or 3 (2k)+1

[digital kettle]

Yeah

Got it

[noble jay]

are you saying 6n+1 = 3n+1

waht

[digital kettle]

The former is impossible @wild zinc

[wild zinc]

ya because it's even and > 2

[digital kettle]

Yeah cool

This is harder:

[noble jay]

oh i see, you should've said 6k+1 and 3n+1

and do what mudkip said

[digital kettle]

Each integer of the form 3n+2 has a prime factor of this form

Yeah my bad :p

This is from burton btw

[wild zinc]

do you know modular arithmetic?

[digital kettle]

Yeah lol

[wild zinc]

well think about if it didn't

[digital kettle]

Hmm okay

Oh

All of its prime factors would be of the form 3k+1 then

[wild zinc]

(or 3)]#

[digital kettle]

Prime factors right?

Well 3 could happen

Then the product of the factors would be 1 or 0 mod 3

Which is not 2 mod 3

Right?

[wild zinc]

yes

[digital kettle]

Cool

Thanks

[buoyant pendant]

Can anyone suggest me some books on number theory?

[wild zinc]

what sort of type of number theory?

[finite plover]

If you are looking for Algebraic Number theory, I read " An introduction to the theory of numbers" from Hardy and it was pretty good.

[opaque merlin]

could someone tell me if there is a formula or something where I multiply any number and it will always equal 1

I require it for my program but I cant seem to find anything on google

[ebon frigate]

The inverse?

k x 1/k = 1

[opaque merlin]

@ebon frigate Im making an audio visualizer and I got 256 bands and I want each band to be different colours but the problem is that the range for each colour is 0-1

I need to somehow multiply numbers from 0to 256 where max is 1

and min is 0

[ebon frigate]

Divide by 256

[opaque merlin]

how would that work. Min value would be 1 then

oh wait

[ebon frigate]

0 divided by 256 is 0.

[opaque merlin]

lol so simple

how did I not see that

[flint pumice]

u cannot divide by 0 😉

[opaque merlin]

thx

[tight topaz]

anyone know how to solve this?

[digital kettle]

hey

is

$$\gcd(a,a+n) = \gcd(a,n)$$

[digital kettle]

?

<@&286206848099549185>

even though no one seems to help me nowadays....

oh wait

NVM IM SO STUPID

sorry lol

just euclidean algo

😅

[wild zinc]

@tight topaz P

[tight topaz]

I thought it would be P or A

can you run it through me?

[wild zinc]

if you look at the number in the alphabet that each letter is

[tight topaz]

Y = 25
E = 5
A = 1
U = 21

[wild zinc]

ya

Y to E is go back 20

wait

I think I mixed up two series in my head :^)

[tight topaz]

no worries 😂

I've been trying to solve this question for about an hour

the answers are:
L = 12
A = 1
P = 16
R = 18
W = 23
to hopefully save you some time

[wild zinc]

cheers

ok

in each case, you multiply by 21 (inverse of 5 mod 26) and mod 26

unfortunately

that gives you the next answer as Y :^)

[tight topaz]

yeah ikr

I even did like 25-5+1 = 21

thus 5-1+21 = 25 = Y

problem I think is that it doesn't factor in the incremental decrease of 4 as well

but ¯_(ツ)_/¯

[wild zinc]

do you have any sort of other questions of this type or any instruction on how to do it?

because there are clearly multiple patterns and idk what kind of thing it couldn't be looking for

[snow basin]

Hi

what is your favorite proof of the law reciprocity quadratic?

exist more of 200!!

[sacred junco]

[glad nacelle]

The Gauss sums proof is p cool

[snow basin]

@sacred junco My english is bad, sorry!

[solar vale]

@snow basin that's quite a factorial right there

[vivid sonnet]

Is 0 actually the 0 we think it is?

[hot vortex]

depends, what do you think 0 is

[vivid sonnet]

what if there's -0

definition of infinity?

[hot vortex]

while I’m 100% certain you’re meming, there certainly are axiomatic systems where such a thing might make sense

[vivid sonnet]

I'm actually not.

[hot vortex]

but for the real numbers, 0=-0

which follows quite easily from the axioms of the real numbers

the relevant axioms are:

1. there exists a number (which we call 0) such that x+0 = x, for all real numbers x
2. for every real number x, there exists a number (which we call -x), such that x + (-x) = 0

these are things we decided

[vivid sonnet]

So let's have a look at pi

[hot vortex]

and under those rules, 0=-0

[vivid sonnet]

Apperently, the number gets longer and longer u kno

[hot vortex]

basically, the real numbers are very well-understood

they’re also more than just a collectionof things we’ve always been calling numbers

[vivid sonnet]

BUT, that if you could see that change happening to a peace of wooden stick (the thing with the chsnging number n stuff)

[hot vortex]

they’re constructed using rules we set into stone, and thus we know the rules of the game and can explore them

[vivid sonnet]

What if you could have a look at it in microscopic sight or even smaller, would you see a change each second?

An increase or decrease?

[hot vortex]

I don’t think you understand how numbers work at all?

pi isn’t changing

[vivid sonnet]

Shh

[hot vortex]

it also doesn’t get longer and longer

it’s always the same

[vivid sonnet]

Numbers are made up things if u think about it

[hot vortex]

pi never changes

you know what

I’m not discussing this further

I have better things to do

sorry

also I don’t think this is the right channel

[vivid sonnet]

K den

[sacred junco]

._.

[sturdy dirge]

And ?

[sacred junco]

I solved the twin prime conjecture

[mossy folio]

God friggin' finally.

[wild zinc]

what took you so long?

[sacred junco]

[wide schooner]

what a go

d

[sacred junco]

Ikr

[dusky egret]

Hello I'm having problems with modulo arithmetic specially when the mod is big and not made up of purely prime numbers

so for example let's say I want to find a congruent ? mod(539)

I know 539 = 11 * 7^2

if it were only 11 * 7 for example I'd split it into two congruence equations one modulo 11 and the other modulo 7 by the Chinese Remainder Theorem

but because I have 7 * 7 I'm not sure what to do

[wild zinc]

one modulo 11, the other modulo 49

also iirc there is a version of the chinese remainder theorem that can work when the moduli aren't coprime but I don't remember what it is off the top of my head

[dusky egret]

hm well I'll google that then, I recall something like it

also how do you solve something of the form x^2 congruent 6 mod(19)

by checking manually and checking if there's a pattern?

[wild zinc]

ya I think you have to do it manually, there might be other ways but idr them right now

[dusky egret]

alright I'll check then thanks!

[unborn horizon]

x ≡ 8 (mod 12)
x ≡ 5 (mod 9)
x ≡ 14 (mod 15)

how do i solve this using the chinese

i was told i have to simplify them

by splitting mods

but i can't find a guide on it

[pine fiber]

Modulo is basically dividing a certain number and using the remainder

[wild zinc]

you know that x = 2 (mod 3)

you can probably simplify using that

[noble jay]

@dusky egret since 19 is prime and x^2 -9 = (x-3 )(x+3)

then 19 divides the first one -or- the second one

then your solution is 19k +3 and 19k -3

and if you have this case for example
x = 1 mod 5
x= 1 mod 2
then automatically. without any chinese needed you can multiply 5 by 2 because 5 and 2 are coprime

[sacred junco]

Dusty number theory god : ^)

[noble jay]

noo

you're not getting those solutions @sacred junco

[sacred junco]

wut

[noble jay]

so how's your "brute forcing" going

it's been 2 months almost

[sacred junco]

Well I’m still trying to brute force the 2016xy one

I mean I haven’t really been working on it lately

[noble jay]

hint theres only a few solutions

[sacred junco]

ya I found like two I think

[noble jay]

jk

theres an infinite amount

have fun

[sacred junco]

._.

[unborn horizon]

@wild zinc so i basicly divide it by 4 without altering the x?

[noble jay]

@unborn horizon first of all you dont" divide" in congruence
second of all x= 8mod 12 translates to 12 divides x-8
but we know that 4 and 3 both divide 12

so 3 and 4 both divide x-8

[unborn horizon]

ohhh

so i can write it that way instead?

x ≡ 8 (mod 12)
x ≡ 5(mod 9)
x ≡ 14 (mod 15)

they give us similar modules

and ask for CRT, but did not show how to get them prime

[noble jay]

ooh

yeah sorry i did not get the question

then forget about what i wrote

[unborn horizon]

nah its okay, i appreciate all the help i'm getting here

[noble jay]

you need to look for a solution to that system first

[unborn horizon]

thats done by using the crt?

[noble jay]

no i mean find one using the euclidian algorithm

[unborn horizon]

just one?

[noble jay]

basically write them as 15y + 8 = 9z +5 and solve that

[unborn horizon]

x is -1

y*

z is -1

[noble jay]

i mean in terms of k like a diophantine equation

[unborn horizon]

let me look that up

[noble jay]

but anyway for 2 of these equations, lets say you found that
x = 14mod9
x = 14 mod 15
then 15 divides x-14
and 9divides x-14
that means lcm(9,15) divides x-14

[unborn horizon]

3 divides x-14?

[noble jay]

least common multiple

of 9 and 15 is 45

[unborn horizon]

ohh

but were did you get x=14mod9

[noble jay]

x =5 mod 9

x= 5+9 mod 9

[unborn horizon]

didn't know that was allowed

makes senve

[noble jay]

x = y + (z times whatever) modulo z
if x= y mod z

[unborn horizon]

so i can rewrite them using that

[noble jay]

yes

[unborn horizon]

until i get something

that is usable in crt?

[noble jay]

until you get a common solution

[unborn horizon]

x=a1m1n1+a2m2n2?

so on and so forth

[noble jay]

instead of manually trying to find that solution

you can solve a diophantine equation

you can rewrite those congruences as 8 +12 a = 5 + 9b = 14 + 15c
and solve for 2 of them

[sacred junco]

[unborn horizon]

diophantine equation works for 3?

including the 14+15c?

[wheat elbow]

yes

[unkempt hedge]

If a^2 = b * c where b and c are relatively prime, does that mean that b and c must be a square? <@&286206848099549185>

[tribal briar]

Yep

[unkempt hedge]

Ok

that is pretty cool 😃

[tribal briar]

Write the prime decomposition

The result becomes pretty clear

[unkempt hedge]

I tried a few examples, and it looks reasonable.

Just wanted to make sure that I was not incorrect.

[wild zinc]

still works when gcd(b,c) is a square iirc

and there are similar results for whatever gcd(b,c) is

[carmine bobcat]

Could anyone help:

Let's call a triplet of natural numbers "obscure" if one cannot uniquely deduce them from their sum and product. For example, {2,8,9} is an obscure triplet, because {3,4,12} shares the same sum (19) and the same product (144).
Find a triplet of ages {a,b,c} that is obscure and stays obscure for three more years: {a+1,b+1,c+1}, {a+2,b+2,c+2} and {a+3,b+3,c+3}.

[silver solar]

I guess they need to be distinct

Otherwise you could take a triplet of the same number :)

[sturdy dirge]

Write the equations.

[carmine bobcat]

How does a triplet of the same number work?

@sturdy dirge any hint?

[sturdy dirge]

Not clear.

$$2+8+9=19, 2\cdot 8 \cdot 9=144$$ And $$2+1=3, 4= \frac{8}{2}, 12=9+3$$ ?

[carmine bobcat]

So you are not clear about the question, or are you giving a hint to the solution?

[sturdy dirge]

Why 3, 4, 12 ?

[carmine bobcat]

3 + 4 + 12 = 2 + 8 +9, and 3x 4 x 12 = 2 x 8 x 9. Hence, {2,8,9} is an obscure triplet

[sturdy dirge]

Then $$a, b, c$$ is obscure if there exists $$\alpha, \beta, \gamma$$ such that ...

[sturdy dirge]

1, 2, 3 sum 6, prod 6 then with 3, 2, 1, we have that 1, 2, 3 is obscure. Correct ?

[carmine bobcat]

No, {1,2,3} and {3,2,1} are considered the same triplet...

[silver solar]

http://www.research.ibm.com/haifa/ponderthis/challenges/July2018.html

[sturdy dirge]

Write a program and solve it by brute force.

[unkempt hedge]

How can I prove that (a^2 - b^2) == 0 (mod 8) when a and b are odd numbers <@&286206848099549185>

I know I can represent a and b as 2n + 1, 2m + 1 respectively.
where n, m N

so you end up with 4(n^2 - m^2) which is not == 0 (mod 8) because (n^2 -m^2) must be == 0 (mod 2).
but we have for example n = 2 and m = 1 which gives us that (2^2 - 1^1) == 1 (mod 2) which is not true

what did I do wrong?

[sturdy dirge]

Study by cases.

[ebon frigate]

(2n +1)^2 - (2m+1)^2 ≠ 4(n^2 - m^2)

You are missing two terms.

[unkempt hedge]

lol

I see it now

thanks

i substituted out 2 from (2(n+m) + 2) and forgot about the 2 and got 2(n+m)

[surreal venture]

You should just think about 1, 3, 5, 7 mod 8. Those are your only possibilities for odd numbers. Squaring all of those gives you 1 mod 8. You should think of this as the units of Z/8Z and this shows you that it's Z/2z X Z/2Z.

When working with modulo arithmetic for an explicit number, if it's feasible use numbers.

[prime axle]

how can i solve this: 6^50 mod 10?

[sacred junco]

Last digit of 6^x is always 6 kek

[silver solar]

If you can write a computer program you can just iteratively multiply 6 by itself 49 times while taking mod 10 at every step

[fringe knot]

why tf would you do that when you know it's always 6

6 -> 36 -> 6 -> 36 -> ...

[silver solar]

Only works because it’s mod 10

[fringe knot]

it's going to cycle for any two numbers

[silver solar]

... no

[fringe knot]

🤔

for any finite integers a and b, x := (x * a mod b) eventually collapses into a loop

[silver solar]

I can agree

But the length of that period isn’t 2 for any number other than 10

[fringe knot]

100

no

25 mod 100

[silver solar]

Not for every, I meant to say

[fringe knot]

yeah, not always a cycle of two, but always a cycle

[silver solar]

Ya

[fringe knot]

btw I'm pretty sure a lot of programming languages have modulus powers built in

I know python does

[silver solar]

That function basically does what I just described right

[fringe knot]

yeah

well it behaves the same way

I'd assume it uses the same method

[wild zinc]

it doesn't

I'd guess it uses something like repeated squaring to reduce the number of multiplications needed to O(log2(exponent)) rather than O(exponent)

[silver solar]

oh yeah fair point

[ebon vine]

No. of positive integers less than 1000 with sum of digits divisible by 7 and the number itself divisible by 3?

[swift shard]

If the number is divisible by 3, then the sum of its digits are divisible by 3. Thus we're looking for numbers that have a digit sum divisible by 21.

Number of ways to partition 21 into 3 numbers?

[unkempt hedge]

What is a good way of finding the amount of solutions to this if the domain of a [1,2,3,4,5,...,8,9] and b, c [0,1,2,3,4,5,6 ... , 9] <@&286206848099549185>

and the +- part can be different

so -a + b -c is a possibility

[ebon vine]

@swift shard thanks

[royal zodiac]

@unkempt hedge Permutation on a elements for where b and c are 0 since a is a nonzero set. Take into account negative counterparts as well

Look at b when it is zero separately and its solutions for ±a and ±c then do the same for c. Basically a contrived permutation problem

[unkempt hedge]

hmm

I don't quite get what you are doing @royal zodiac , I would say that you are just finding all permutation for a=1, a = 2 and a =3 and so on. so you have that b + c = 1, b + c = 2, b+c = 3 and so on until you get b+c = 9 right

This is the original question, and now that I think about it the number of negative signs should be 1 because divisibility rule for 11 is the first minus the second plus the units digit equals 0.

[royal zodiac]

I was thinking that was set theoretic notation since you had the intervals comma separated and then you would take into account for ±a and ±c when b=0 and ±a and ±b when c=0 to yield 0 as an answer when ±a±b±c were multiplied

How is this tying in with the question you posted?

Oh, I see now. It's a string of operations, not being multiplied

That should have been clarified

[unkempt hedge]

I was thinking that N [100, 999] and N = abc , abc denotes the number and its digits. for a number to be divisible by 11 the alternating sum of its digits must equal zero. for example 121 is divisible by 11 because 1 - 2 + 1 = 0 . so if we want to find our how many numbers N is a permutation that is divisible by 11 +-a +-b +- c = 0 or rather WLOG a - b + c = 0, idk

[royal zodiac]

You consider cases of viability. For that interval there are 8 multiples of 11 (nonzero digits) and all 8 give valid permutations hence 24 as the first case. The we take into account the multiples of 11 with zeros in the digits which are 9 in total for the interval we are working with: 110, 220, 330, 440, 550, 660, 770, 880, 990 and only 2 give valid permutations so 18. Now, if the digits are different from one another then you have 81 multiples of 11 in [100,999]. From the 8 in the first case and the 9 in the second case we have 64 multiples of 11. Out of these 11, 8 of them have a zero-containing digit sequence: 209, 308, 407, 506, 605, 704, 803, 902 which has 4 permutations which work. With the 8 zero containing digit sequences you then multiply by 2 since permutations overlap by a factor of 2 due to us finding digit sequences which are also permuted as a multiple of 11 which then yielding 16. The 64 from earlier when subtracting 8 and 9 from 81 is now subtracted by 8 zero containing digit sequences previously for eliminating results thence to 56 because we do not want the zero containing digit sequences. The 56 multiples of 11 all have, now, 3! permutations which work because of the 3 digits which are nonzero, valid by checking from some random nonzero multiples of 11 in the interval. This yields 6 but again, the permutations overlap by a factor of 2 because for abc being a multiple of 11, it overlaps as well with different permutations of abc. therefore 56*3 yields 168 remaining permutations which work. Add them up from the previous cases to now. They are highlighted for accessibility. 169+16+18+24=226 valid permutations in all

You can set up a chart as well for the plain multiples in [100,999] to check for yourself but it is hasslesome

Brute-force doesn't work here, however, checking the viability with a calculator does

Maybe for checking multiples, modular arithmetic can come in handy and check for remainder

[unkempt hedge]

wow this is a lot of text

[royal zodiac]

Yeah, well, number theory can suck like that sometimes

[unkempt hedge]

I would say this is more of a combinatorics question tbh.

the number theory is just how you get the equation in the beginning

[royal zodiac]

Yeah it is combinatorics but it runs off of number theory

[unkempt hedge]

true

[unkempt hedge]

@royal zodiac I have been looking at your answer for a while. (It is too dense to actually get what you are talking about).

From what I have gotten out of it we have 121, 242,484 and 110, 220, 330, ... 990 have 2 permutations so

I get (81-3-9) * 3 + 2 * 3 + 2 * 9 = 231 what am I missing?

[royal zodiac]

(81-8-9) for starters

Also, why are you multiplying by 9?

[unkempt hedge]

there are 9 "elements" 110, 220, 330, ... 990

with 2 permutations

[royal zodiac]

Oh yeah

We derived 18 from that

[unkempt hedge]

What I am thinking is that you have 81 different numbers that is a multiple of 11 from 100 to 999. and there are 3 numbers which have 2 permutations 121, 242,484. and 9 110, 220, 330, ... 990 which also have 2 permutations. Therefore you take away those from 81 and multiply by 3 since the rest "I belive" to have 3 permutations. So we end up with (81-3-9) * 3 + 2 * 3 + 2 * 9 = 231

[royal zodiac]

3 numbers with two permutations which are nonzero digitally?

[unkempt hedge]

"nonzero digitally" ?

[royal zodiac]

You subtract 8 and 9 from 81 for the case where the digits differ

So where exactly is 3 coming up?

[unkempt hedge]

I am thinking that A = "81 different numbers which are a multiple 11". then 121, 242, 484 A. and since they don't have 3 permutations. we do 81 - 3 and outside we do + 3 * 2 .

[royal zodiac]

No because we already inspected the case where two permutations exist for the ones which are nonzero digit-wise and zero digit-wise

121, 242, and 484 are not the only digit sequence that only have two permutations for 11

[unkempt hedge]

Ok, but I think I am doing it differently from you. Just tell me are there more numbers with 2 permutations other than 121, 242,484 110, 220, 330, ... 990 ?

[royal zodiac]

yes

[unkempt hedge]

which?

[royal zodiac]

363, 616, 737, 858, 979

[unkempt hedge]

oh, ok

yes we can also have a b c = 11

it just needs to be congruent to 11

or 0 (mod 11)

ok so then I get the right answer (81 - 5 - 3 - 9) * 3 + 2 * 5 + 2 * 3 + 2 * 9 = 226

@royal zodiac Thank you for you help, I feel like I have learned something new 😃

[royal zodiac]

👍

[cunning stump]

How do I find x

8x conj 9(mod 41)

[versed storm]

multiply both sides by 5 to get -x = 4 (mod 41). So then x = -4 = 37 (mod 41)

[rancid oasis]

Folks I have made a breakthrough

I have discovered that $$n = 2^k \frac{2^{\ell+2} - 1}{2^{k+2} - 1}$$ has natural solutions when $$\ell + 2$$ is a natural multiple of $$k+2$$

[rancid oasis]

It appears all of these solutions are in fact the same solutions my simulation obtained

Now I just have to prove this property

[vast vessel]

@rancid oasis geometric series

[rancid oasis]

I don't follow

[vast vessel]

=tex \frac{a^b-1}{a-1}=1+a+a^2+a^3+\dots+a^{b-1}

@rancid oasis

[rancid oasis]

Thank you but I'm still a little lost on how I can use this

It makes sense, and I can see I can simply substitute $$a=2^k$$

[vast vessel]

Let a = 2^(k+2)

[rancid oasis]

Or yeah $$a = 2^{k+2}$$

[rancid oasis]

The results of our work last night:

On the other hand, if $$n$$ is even, the solutions can be generated when $$\ell + 2$$ is some natural multiple of $$k+2$$. This can be shown by the following induction:
\begin{align*}
\frac{2^a - 1}{2^b - 1} &= 2^{a-b} + \frac{2^{a-b} - 1}{2^b - 1}\
&= 2^{a-b} + 2^{a-2b} + \frac{2^{a-2b} - 1}{2^b - 1}\
&= 2^{a-b} + 2^{a-2b} + 2^{a-3b} + \frac{2^{a-3b} - 1}{2^b - 1}\
& \hfill \vdots \hfill \
&= 2^{a-b} + 2^{a-2b} + 2^{a-3b} + \cdots + 2^{a-cb} + \frac{2^{a-cb} - 1}{2^b - 1}
\end{align*}
When $$a-cb < b$$, we are left with two possibilities: either $$a-cb = 0$$ and the last fraction disappears, or $$a-cb > 0$$ and the last fraction becomes some decimal. If we define $$b = k+2$$ and $$a=\ell+2$$ we can see that in the second case, even multiplying by $$2^k$$ will not make the fraction into a natural number, as $$2^k$$ is not divisible by $$2^{k+2}$$, nevermind $$2^{k+2} - 1$$. Thus we can see that $$a-cb =0$$ for some natural number $$c$$, meaning $$a$$ must be some natural number multiple of $$b$$. Thus we obtain all the even solutions for part 2:

\begin{equation}
n = 2^h \frac{2^{g(h+2)} - 1}{2^{h+2}-1}
\end{equation}

where $$g,h$$ are any natural numbers. Indeed, this also includes the odd solutions, as we must simply set $$h=0$$ and we will obtain the exact same results as equation (9).

[vast vessel]

@rancid oasis second paragraph typo: a-cb < b

[rancid oasis]

OUF

[vast vessel]

👌

[rancid oasis]

Perfect. Thanks

[vast vessel]

k

[worthy sable]

I'm trying to find, in terms of two positive integer constants a and b, the number of unique positive integer solutions (x, y) to the equation $$x^2+ax=y^2+by$$. I've tried multiple approaches but can't seem to get an answer... any ideas?

[velvet frigate]

you could complete the square

[worthy sable]

i tried that but it only gives extra terms

unless im missing something

[velvet frigate]

should be something like 4(x-u)^2 = 4(y-v)^2 + k

and you should be able to simplify this with a change of variables to something like 4x^2 = 4y^2 + k

and so k is 4 times the difference of two squares

and so on

[worthy sable]

Nice, now I have $$(2x+2y+a+b)(2x-2y+a-b)=a^2-b^2$$

[worthy sable]

But now how might I express the number of solutions in terms of a and b when they are on both sides?

[velvet frigate]

how did you get this

[worthy sable]

with your method

the difference of two squares as a product

i got $$(2x+a)^2-(2y+b)^2=a^2-b^2$$

[velvet frigate]

that looks better

now we would like to do a change of variable x -> x - a/2 and y -> y - b/2

but this only works if a and b are even

hmm im not sure

[worthy sable]

i think they have to be the same mod 2

so x = a (mod 2) and y = b (mod 2)

x > a+1 and y > b+1

[velvet frigate]

oh hang on you have x and y positive

that should be easier

a^2 - b^2 = c^2 - d^2 only if a = c and b = d I think?

when all of them are positive

[rain rampart]

you solve by simultaneous equations

factorize the LHS and RHS so you have
$$(2x+a-2y+b)(2x+a+2y+b) = (a-b)(a+b)$$

[rain rampart]

Then for integer solutions:
$$2x+a-2y+b=a-b$$
$$2x+a+2y+b=a+b$$

[rain rampart]

$$2x+a-2y+b=a+b$$ or
$$2x+a+2y+b=a-b$$

You can also have
$$2x+a-2y+b=1$$ or
$$2x+a+2y+b=(a-b)(a+b)$$

[rain rampart]

some of the simultaneous equations won't work so they won't have a solution since you need positive integer solutions

[rain rampart]

looking at your question again, i believe you've made errors in factorising, so you need to check on that first

[serene ferry]

What are some cryptographic functions (like hashes) for encryption, I could take a look at?

[broken blade]

@serene ferry anything specific you're looking for?

[north orbit]

A set S of distinct positive integers has the following property: for every integer x in S, the arithmetic mean of the set of values obtained by deleting x from S is an integer. Given that 1 belongs to S and that 2002 is the largest element of S, what is the greatest number of elements that S can have?

I'm a little stuck with this question

Let's say n is the number of elements in S

and N is the sum of all the integers in S

then we know that n-1 divides N-x so N = x (mod n-1)

I don't really know what to do now. And also you can say N = 1 (mod n-1) or N = 2002(mod n-1) since they said that 1 and 2002 are in S

[velvet frigate]

that means that 1 = 2002 (mod n-1)

so that 0 = 2001 (mod n-1)

n-1 must then divide 2001

and 2001 is 2 * 3 * 23 * 29

[north orbit]

So then n-1 = 29?

[velvet frigate]

well it can be 2001 as well

or any other divisor

it doesn't need to be prime

[north orbit]

Oh right

[velvet frigate]

now if you add some number x, then by the same arguments you have x = 1 = 2002 (mod n-1)

this seems to say a lot

[north orbit]

How did you get that?

[velvet frigate]

N = x (mod n-1)

for any x

in particular N = 1, N = 2002, N = x

[north orbit]

Oh ok

[velvet frigate]

it says that... what does it say

that we have 2001/(n-1) - 1 slots to put the elements in

so (n-2) <= 2001/(n-1) - 1

this inequality should give a nice bound for n

[north orbit]

What do you mean by we have that many slots to put the elements in?

[velvet frigate]

because 1 < x < 2002 and 1 = x = 2002 (mod n-1)

so x can be 1 + (n-1), 1 + 2(n-1), 1 + 3(n-1) ...

(n-2)(n-1) <= 2001 - (n-1)
(n-1)^2 <= 2001
so we get n <= 45

so that n can be 2, 3, 6, 23, 29

2 works, 3 doesn't

you'd have to test the others

using the fact that your numbers x can be any of 1 + k(n-1)

[north orbit]

Sorry I'm still not understanding why (n-1) < 2001/(n-1) -1.

[velvet frigate]

there are 2001/(n-1) - 1 possible elements between 1 and 2002 which are equal to them mod n-1

oops it's n-2

fixed

but yeah

out of the n-2 elements remaining, you have to choose them out of the 2001/(n-1) - 1 possible ones

[north orbit]

Why n-2 now?

[velvet frigate]

there's n elements, 2 of them are 1 and 2002

the rest you choose from the slots

[north orbit]

Oh but your first statement with 2001/(n-1) -1 is still correct?

[velvet frigate]

yeah

those are the number of slots

[north orbit]

And those would be number of slots for x?

[velvet frigate]

yeah

[north orbit]

Ok here's what I am understanding. So 1 <= x <= 2002

and we know x=1=2002 (mod n-1)

So, like you said, 1 + k(n-1)=2002 meaning k = 2001/(n-1)

[velvet frigate]

yeah

but 2002 is already taken

so -1

[north orbit]

Wait shouldn't we add 1 since x can be 1 or 2002?

[velvet frigate]

x can't be 1 or 2002

those are already taken

[north orbit]

Can't you still delete 1 and 2002 from S?

[velvet frigate]

no

[north orbit]

Are we saying that x is the integer that we are removing from S?

[velvet frigate]

we are analyzing where the other n-2 elements of S can lie

they must fit in those 2001/(n-1) - 1 slots

[north orbit]

Ok makes sense

And then once you get your list of n that may work, you check to see if 2002 can equal 1 + k(n-1) ?

[velvet frigate]

no, that condition is always true

for divisors of 2001

you'll have to try other stuff from there

[north orbit]

So we're just finding the largest value of (n-1) that divides 2001 but is less than 44?

[velvet frigate]

no, we need to check that it works

there's more work to do

for now, the candidates are 1,3,23,29

[north orbit]

What are you checking it against?

And where are you getting those candidates from? Aren't they supposed to be factors of 2001?

[velvet frigate]

yeah

those are the smallest factors of 2001

hang on...

the 2 is extra lmao

[north orbit]

Ok so should be just 3, 23, and 29

[lyric adder]

this is going on for awhile

[velvet frigate]

1, 3, 23, 29

yeah it's going to go on still, I don't see a clear way to complete the problem from here

I imagine 29 works though

gotta show that

[north orbit]

And I don't get what we have to check for

Why aren't all of those valid (n-1)

[lyric adder]

what properties do you have for n? (n-1) | 2001 and what else

[velvet frigate]

you have to give a set of n numbers that satisfies the conditions

we haven't imposed all the conditions yet

A set S of distinct positive integers has the following property: for every integer x in S, the arithmetic mean of the set of values obtained by deleting x from S is an integer. Given that 1 belongs to S and that 2002 is the largest element of S, what is the greatest number of elements that S can have?

[north orbit]

Is that something you have to prove with sets or something?

[lyric adder]

@north orbit we want to think of things that characterize n

[velvet frigate]

not sure, again I'd try stuff by expressing each element as 1 + k(n-1)

and seeing how the sum of them behaves when you take each one out, etcetera

[north orbit]

I guess I don't understand why our values of (n-1) don't always satisfy the conditions

[velvet frigate]

for example for (n-1)=3 you have n=4 and so you have two elements 1 + 3a and 1 + 3b

the sum is going to be 1 + 2002 + 1 + 3a = 2004 + 3a

and in every case it's divisible by 3 and you win

[lyric adder]

you have N = x (mod n-1) for any x in S right?

yeah

[north orbit]

Yeah

[velvet frigate]

oh maybe that condition is enough

yeah it is

nice

[lyric adder]

i think it is

[velvet frigate]

so yeah 29 is the answer

[north orbit]

So n = 30

[velvet frigate]

uhuh

[north orbit]

How do you know that all of the conditions are met?

[velvet frigate]

take 28 extra elements of the form 1 + a_i (n-1), doesn't matter which

if you take one element out of S and calculate the sum, you get...

sum[ 1 + a_i (n-1)] + 1 + 2002

= (n-1) + sum[a_i] (n-1) + 2001

which is divisible by n-1

[north orbit]

Wait which condition were we not sure was satisfied?

[lyric adder]

this seems oddly messy

i wonder if there's a more elegant way

[north orbit]

that 2001 is divisible by n-1?

[velvet frigate]

for every integer x in S, the arithmetic mean of the set of values obtained by deleting x from S is an integer

[north orbit]

Well wouldn't that be satisfied since we defined our congruences based on that?

[velvet frigate]

I think so

[north orbit]

Like in the beginning we said that N=x(mod n-1)

[velvet frigate]

yeah

[lyric adder]

N is the sum of the elements in N with x deleted?

[velvet frigate]

and that implies some things that we used

yeah it's the sum

but we didn't use the full power of N=x for all x

[north orbit]

No N is the sum of everything in S

That's how I defined it at least

[lyric adder]

then is it true that N = x mod n-1

[north orbit]

Yeah

[velvet frigate]

we need that yeah

[lyric adder]

?

[velvet frigate]

because N-x is divisible by n-1

[lyric adder]

oh duh

so the sum is congruent to every thing in the set mod n-1

ok

[north orbit]

So in general with any problem like this, how do you know all of your conditions are met?

[velvet frigate]

you prove it

you don't know until you prove it

though you might have a hunch

like we had a hunch that the stuff we imposed was enough to have 29 work

[lyric adder]

i dont like what we have

there's got to be an easier way to do this

[velvet frigate]

why

it was straightforward enough

[lyric adder]

what did you do?

you bounded it from above somehow or something

[velvet frigate]

notice that N = 1 = x = 2002 (mod n-1), which along with 1 < x < 2002 gives us an upper bound on n

[north orbit]

I've been running into a lot of problems where I'm not sure if all of the conditions have been met. And these are AMC/AIME problems so I don't think they are expecting for you to prove everything

[velvet frigate]

they are, the proof is simple

in this case, I outlined it above

take 28 extra elements of the form 1 + a_i (n-1), doesn't matter which if you take one element out of S and calculate the sum, you get... sum[ 1 + a_i (n-1)] + 1 + 2002 = (n-1) + sum[a_i] (n-1) + 2001 which is divisible by n-1

[lyric adder]

i mean 2001 = 0 mod n-1 gives us possibly 8 numbers n can be

i wonder if you can prove n-1 is prime or something

[velvet frigate]

nah it's not about primality

you can pick a number other than 2002 for the problem

one with many factors

and get a composite answer

[north orbit]

And the reason we haven't proved that is because we didn't let x be any number?

[velvet frigate]

what?

the reason we haven't proved it is before we didn't try to prove it at any point

we just imposed some conditions

[lyric adder]

how do you throw out a number?

like why doesn't 667 work

[velvet frigate]

because there aren't enough different numbers

to get 667 of them

your options are

[lyric adder]

can you not have repeat numbers?

[velvet frigate]

1, 668, 1335, 2002

you can't

if you can have repeat numbers, then just pick n-1 = 2001

and choose 1, 2002, 2002, 2002, ...

[lyric adder]

ah

ok so

why arent there enough different numbers?

[north orbit]

we imposed conditions based on what the problem gave us so isn't it just given?

[lyric adder]

why did he take multiple of n

or n-1 rather

[north orbit]

Which part of the solution are you on?

Are you following the previous solution?

[lyric adder]

im seeing what excludes these larger numbers

i feel like this has a simpler solution though

where did you see this problem?

[north orbit]

If you want to look at some other solutions, this is AIME I 2002 Problem 14

[lyric adder]

solutions to this problem?

[velvet frigate]

to see why there aren't enough, try n-1 = 667

the options are 1, 668, 1335, 2002

since the elements have to be equal to 1 and 2002 mod 667

so only 4 elements

[lyric adder]

i see

[north orbit]

Well thank you very much for the help @velvet frigate

[lyric adder]

why is the greatest element at least (n-1)^2 + 1?

[velvet frigate]

because the smallest you can pick are, in order, 1, 1 + (n-1), 1 +2(n-1) ... 1 + (n-1)(n-1)

[lyric adder]

i see

does that solve it?

doesnt*

[velvet frigate]

that gives you the same bound as before

n < 45 approx

[lyric adder]

yeah

[velvet frigate]

and so if you show that any of the smaller n works, that's all

[lyric adder]

well

you need to show n=29 works

[velvet frigate]

sure

[lyric adder]

showing n=3 still leaves the question of n=29

do you need to like find a set of 29 to prove this

[velvet frigate]

nah just show any set of 29 works

[lyric adder]

any set/

[velvet frigate]

by writing the elements as 1 + a_i(n-1)

[lyric adder]

?

[velvet frigate]

yeah

[lyric adder]

oh

[velvet frigate]

they all work

[lyric adder]

really

nice

[velvet frigate]

yes

[outer brook]

Hey I'm sorta a noob to number theory, but is there a way to prove generally, integer solutions of a diophantine equation such as (x^n+a)/b=y, where you are given some arbitrary n, a, and b,

[serene ferry]

@broken blade Not anything specific, just some 'interesting' functions.

[lyric adder]

@outer brook you're asking specifically about diophantine equations of that form?

@outer brook respondng to the "prove generally" there are proofs of the solutions of different classes of diophantine equations

[outer brook]

Give me links pls

[lyric adder]

Im not really sure what you're after

like ax + by = c?

i would figure you know about that one

[outer brook]

Yes but I'm talking about polynomial cases

[versed storm]

1 solution

[sturdy dirge]

Is it unique ?

[lyric adder]

what kind of question is that.

"is it unique"

no there are multiple maximum values n can attain?

[outer brook]

Easy

Maybe he read it as possible values of n

[carmine ingot]

I don’t know, that’s all the question said.

[outer brook]

A+B=n, A^2+B^2=n+19

[sturdy dirge]

$$\iff \left{\begin{matrix}A+B&=n\AB&=\frac{-19}{2}\end{matrix}\right.$$

[north orbit]

a = (4d^2-30d)/(30-3d)

If a and d are positive integers, find all possible pairs of a and d

[unkempt hedge]

I don't know what is wrong here.
13x+11y = 700
has the solution 700 = 1353 + 111
so
x = 53 + 11k and y = 1-13k
if we take into consideration
y = mx - 1
we substitute and get that
1 - 13k = m(53 + 11k) - 1
2 - 13k = m(53 + 11k)
m = (2 -13k) / (53 +11k)
but m has to be a positive integer, so therefore 2 -13k == 53+11k (mod 2), but it is not so there are no solution. But when I looked at the solution there were 2. What is wrong with this statment

@north orbit Let me look at it

[hardy iron]

what did you do at x = 53 + 11k and y = 1-13k

[unkempt hedge]

it is a Diophantine Equation

[hardy iron]

oh to the above equation?

[unkempt hedge]

(yes, if you are referring to my problem)

[hardy iron]

yeah

oh i get it

11*13 cancels

for each k

[unkempt hedge]

(I think it has to do with the substitution part, I don't know)

[north orbit]

@unkempt hedge I gotta go right now, but if you do find a solution to my question, just tag me please and I'll take a look at it later

[hardy iron]

why does m have to be a positive integer?

[unkempt hedge]

@north orbit I probably won't because I am terrible at number theory. but I will try😅

[hardy iron]

couldn't m be a negative integer?

[unkempt hedge]

yes

[hardy iron]

so why did you assume m is a positive integer?

[unkempt hedge]

I didn't

[hardy iron]

sorry, edited

[unkempt hedge]

I didn't assume m was positive

[hardy iron]

you wrote that thou?

unless you're saying i can ignore that part

but m has to be a positive integer, so therefore 2 -13k == 53+11k (mod 2), but it is not so there are no solution. But when I looked at the solution there were 2.

[unkempt hedge]

I said that there are no solutions because this statement is incorrect 2 -13k == 53+11k (mod 2)

by == I mean that they are congruent

[hardy iron]

yup

[unkempt hedge]

but, the solution says that it has 2 values.

[hardy iron]

hold on, why 2 -13k == 53+11k (mod 2)

what if it's 2/1

or 4/1

etc. etc.