elementary-number-theory

[polar ruin]

so can you explain it to me now? :v

[stiff rivet]

explain the application to diophantine equations?

essentially any solution in integers induces a solution modulo m for any m

so if a diophantine equation is not solvable modulo m, it cannot be solvable in integers

checking for solutions modulo m is much easier as there are only finitely many possibilities

[polar ruin]

basically from 6y = 1 mod 23 down

[stiff rivet]

so this is a way to show that certain diophantine equations are unsolvable

[polar ruin]

where did this 4 even come from? :v

[stiff rivet]

its the multiplicative inverse of 6 mod 23

this problem is really weird though

it essentially just asks to compute the bezout coefficients of 23 and 29

there is no reason to look at it mod 23

[polar ruin]

ohh

https://www.youtube.com/watch?v=_rRu1jg7Kus

is this a good one?

[stiff rivet]

no idea, i am not going to watch that video

but you need bezouts identity to compute inverses modulo some number (if they exist)

the actual computation of the coefficients is done (again) using the (extended) euclidean algorithm

[polar ruin]

Ah i just thought maybe u watched him , well I was trying to learn the modulo way because it seems faster than using the euclidean alg
this was me doing an equation

frick wait

https://cdn.discordapp.com/attachments/359052581022203914/883696800207364106/image0.jpg

https://cdn.discordapp.com/attachments/359052581022203914/883696800668733470/image1.jpg

[stiff rivet]

i think anything you can do to solve those kinds of equations just boils down to the extended euclidean algorithm

[polar ruin]

is it an efficient way of solving it?

[stiff rivet]

computationally its the most efficient way we know

[polar ruin]

oh....

so this is bad?

[stiff rivet]

they have to do euclidean division anyway

to compute that 4 is the multiplicative inverse of 6 mod 23

[polar ruin]

owh sounds even more

ugh

[stiff rivet]

maybe in some cases it is easier to see immediately or something

but it boils down to essentially the same amount of work

like, a computer would just do euclidean division of 29 and 23

[polar ruin]

ah what about a non-computer ?

what would he do?

[stiff rivet]

here he has to do euclidean division of 4 by 23

and then the same again

probably the same

maybe there are some tricks for small numbers

but i don't see why you would even ever need to compute this by hand

[polar ruin]

I see thanks for the insight :DDD

[sacred junco]

hello! i was hoping if someone could help me with this question

[quartz needle]

how?

[quartz needle]

How do you guys like my proof of

@quick furnace

[quick furnace]

your handwriting is messy as shit

[quartz needle]

wdym

[quick furnace]

i mean exactly what i said.

it's hard to read.

and it also looks like you're overcomplicating this

but to demonstrate, this is what your a-b and c-d parse as to my eyes

[quartz needle]

ok, maybe a, and d

but

how does b look like h

[quick furnace]

anyway

what was your goal again

$a \equiv b \pmod{m}, c \equiv d \pmod{m} \overset{?}{\implies} a-c \equiv b-d \pmod{m}$

[sterile pumice]

Ann

[quick furnace]

this?

[quick furnace]

okay, yes.

do you allow yourself to use the theorem that if $m|x$ and $m|y$ then $m|(x+y)$?

[sterile pumice]

Ann

[quartz needle]

why not

[sacred junco]

can someone pls help me with this question?

[quick furnace]

okay, if you do, then this matter is trivial

(a-c) - (b-d) = (a-b) + (d-c) by simple algebraic manipulations

[quartz needle]

and?

i did it hin the first line

m|a-b
m|c-d

[quick furnace]

yeah but then you went on to overcomplicate this massively

[quartz needle]

wdym? i just wanted to show that they are all equivalent

[quick furnace]

m | a-b, m | d-c, therefore m | (a-b)+(d-c), therefore m | (a-c) - (b-d), therefore a-c \equiv b-d mod m

that's it

nothing else needs to be said

it's a very simple chain of reasoning

[sacred junco]

can someone pls help me with this q i am kinda dumb lmao

[quick furnace]

this belongs in #prealg-and-algebra not here @sacred junco

[quartz needle]

how do i do

[sacred junco]

tysmm

[quick furnace]

it's going to be a minus some multiple of m @quartz needle

[quartz needle]

x = a -sm, you mean?

[quick furnace]

yes, where s depends on a and m somehow

[quartz needle]

i can give you the solution, which i don't understand

[quick furnace]

oh you have access to the mod function

honestly i would've written it differently

$x = a - \mathrm{round}(a/m) \cdot m$

[sterile pumice]

Ann

[quick furnace]

where $\mathrm{round}(t)$ is the function that rounds $t$ to the nearest integer (be that above or below), and for concreteness i'll say it rounds half-integers up

[sterile pumice]

Ann

[quartz needle]

idk where you got it from, though

[quick furnace]

i'm not about to write down a formal proof

round(a/m)*m is the closest multiple of m to a

[quartz needle]

yeah, how did you come up with that round function

why make s equal to it

[quick furnace]

the minimum of |a - sm| as s ranges over the integers is no bigger than m/2

[quartz needle]

?

[quick furnace]

...

okay so like

let me try to put this another way

if we wanted the smallest POSITIVE integer congruent to a modulo m

that's just a mod m

(or a % m as you would write it in some programming languages)

[quartz needle]

i know why

i just don't know how you connect it

[quick furnace]

a % m = a - floor(a/m)*m

[quartz needle]

smallest positive integer congruent to a modulo m

same number,
lol?

[quick furnace]

??

[quartz needle]

20 mod 3 = 2
5 mod 3 = 2

[quick furnace]

and your point is...?

[quartz needle]

that
20 mod 3 is congruent to 5 mod 3

so the smallest positive integer congruent to 20 mod 3 isn't 20 mod 3

but 5 mod 3

[quick furnace]

????????//ds/.sb.,sd what?

okay, hold on

yes, 20 is congruent to 5 modulo 3

but 20 % 3 isn't 5, it's 2.

[quartz needle]

i'm not syaing that it's 5?

yes, 20 is congruent to 5 modulo 3

[quick furnace]

then what in blazes are you even saying

[quartz needle]

20 mod 3 = 5 mod 3
or equivalently
20 = 5 (mod 3)

[quick furnace]

yes, and? what is your point?

the smallest positive integer congruent to 20 modulo 3 is 2

20 % 3 = 5 % 3 yes because they're both equal to 2

so the smallest positive integer congruent to 20 mod 3 isn't 2
but 2

[quartz needle]

i mean, you are contradicting yourself.
first you have said that

20 is congruent to 5 modulo 3
[11:41 AM] Ann: but 20 % 3 isn't 5, it's 2.
which would imply that
20 mod 3 = 5 mod 3
20 = 5 (mod 3)
aren't equivalent

and then you said

[11:42 AM] Ann: yes,

[quick furnace]

$a \equiv b \pmod{c}$ is not the same as $a % b = c$

[sterile pumice]

Ann

[quartz needle]

i haven't said that though

[quick furnace]

idk if it's your intention but it feels as if you're deliberately getting me more confused and more aggravated until i accidentally say something incorrect that you can then point in my face and accuse me of contradicting myself

i can feel myself getting physically dizzy over this modulo bullshit that you seem to be dense with

idk if your actions really are deliberate

to clear myself of any suspicion that might or might not be cast upon me, i am NOT accusing you of doing anything of this sort deliberately

[quartz needle]

i addressed this point weeks ago

could you please just address this directly

@quick furnace

[quick furnace]

sorry i need some time to cool down

[quartz needle]

like my point is
you have two numbers that are congruent to each other
i think what you are saying is that if you just take one number, say a, and do a mod m, you will receive a remainder
then numbers that are congruent to it have the same remainder
but then you are saying that the smallest integer that is congruent to a mod m is just that remainder
so
(a mod m) mod m is equivalent to a mod m, which makes sense, since a mod m isn't divisible by m, so (a mod m) mod m just returns a mod m

there's only one number that can be the smallest, so it should be a mod m

but
has two cases

anyways, ping me when you'd like to help @quick furnace

[stiff rivet]

this questions asks for the integer with the smallest absolute value

your mod operation gives the smallest positive integer

now x mod m and (x mod m) - m clearly have the same remainder mod m

and you have to check which has smaller absolute value

(all other possibilities clearly have larger absolute value than those two)

@quartz needle

[quartz needle]

smaller absolute value?

but aren't they equal

[stiff rivet]

no

$5 \equiv 2 \equiv -1 \mod{3}$

[sterile pumice]

Lochverstärker

[stiff rivet]

in this case 5 mod 3 = 2 but 5 mod 3 - 3 = -1 has smaller aboslute value

[quartz needle]

ok

what's up with the ceil(m/2), though?

[stiff rivet]

this checks which of the two values has the bigger absolute value

[quartz needle]

yeah, but where does it come rfom

[stiff rivet]

it comes from the fact every mth number is in the same equivalence class mod m

so of the two values closest to 0 (which you consider here) one has distance < m/2 from 0

[quartz needle]

you mean congruence class?

[stiff rivet]

yes

[quartz needle]

i still don't understand

[quartz needle]

oh i see

[stiff rivet]

in this case a = a mod m

and either a or a-m must be closer to 0

its the one which has distance less than m/2

[quartz needle]

what's the point of the cieling function

[stiff rivet]

deal with the case that m/2 is not an integer

[quartz needle]

why does it matter

you still can compare

[stiff rivet]

ye, but the distance will always be a positive integer

so if you dont ceil/floor you dont consider every case

[quartz needle]

?

[stiff rivet]

if m=5, then m/2 = 2.5 and the two cases arent exhaustive

actually

[quartz needle]

i mean

just see which one is smaller than m/2

x mod m if x mod m <= m/2 and (x mod m) - m otherwise

[stiff rivet]

actually the solution is wrong i think

[stiff rivet]

this should work

when m is even it doesnt matter

when m is odd the distance of one of those numbers is floor(m/2) and the other distance is ceil(m/2)

you have to take the smaller, i.e. floor(m/2)

so the solution should floor or do nothing

[quartz needle]

what are you saying

the distance isn't floor or ceil

[stiff rivet]

it is

[quartz needle]

?

most of the time the distance is some fraction

[stiff rivet]

it never is

the distance between integers is always an integer

[quartz needle]

oh right, we are only considering integers

ok but say we have
2 and -1

m/2 is 1.5

[stiff rivet]

the distance of 2 from 0 is ceil, the distance of -1 from 0 is floor of that

[quartz needle]

can you prove it

[stiff rivet]

yes

it directly follows from the fact that floor(m/2) + ceil(m/2) = m

actually i am wrong lmao

[quartz needle]

yeah

[stiff rivet]

i was just thinking of the "worst case"

what i actually wanted to say is that one of the distances will always be <= floor(m/2) and the other >= ceil(m/2)

[quartz needle]

ok ty

[quartz needle]

How does it follow

[stiff rivet]

in general, it doesnt

[quartz needle]

@stiff rivet

[stiff rivet]

well, there is a proof given

[quartz needle]

why would n^2 - 1 mean that n^2 is equivalent to 1 mod 8

[stiff rivet]

alternatively there are the cases n = 1, 3, 5, 7 mod 8

thats the definition of modulo

[quartz needle]

right

how do i solve this one?

[stiff rivet]

what have you tried?

[quartz needle]

i just wrote it as
m | a -b
mk = a -b
and
mq = b^k - a^k

[stiff rivet]

mq = b^k - a^k is what you want

so look at b^k - a^k and use what you have

[quartz needle]

what's the point in
b = a - mq
a = mq + b
k = (a-b)/m
mq = (a - mq)^((a-b)/m) - (mq + b)^((a-b)/m)
?

[stiff rivet]

actually careful

you used k twice

in different meanings

[quartz needle]

@stiff rivet

[stiff rivet]

?

[quartz needle]

what's the point

[stiff rivet]

solving the exercise

[quartz needle]

how does

mq = (a - mq)^((a-b)/m) - (mq + b)^((a-b)/m)
help me

[stiff rivet]

it doesnt, because its wrong

k is not (a-b)/m

[quartz needle]

mk = a -b |/m
k = (a-b)/m?

[stiff rivet]

k has nothing to do with a, b or m

its given in the exericse, its just some integer

[quartz needle]

oh right

i see what you mean

let's do it again

m|a -b
mq = a-b
m|a^k - b^k
mz = a^k - b^k

a = mq + b
b = a -mq
mz = (mq + b)^k - (a -mq)^k

[stiff rivet]

you have to show that such a z exists

i suggest calculating (mq + b)^k

[quartz needle]

3 variables?

[stiff rivet]

sure

[quartz needle]

idk how

[stiff rivet]

then you either have to figure out how to or think of a smarter way to solve the exercise

[quartz needle]

can't you help me with either

[stiff rivet]

the former is called the binomial theorem

the latter would just amount to me telling me what to do

your book might have shown something earlier that helps though

[quartz needle]

i don't remember binomial theorem, i know that this book reviews it a bit later

so either you tell me what to do or i skip it

what do you choose?

[stiff rivet]

i don't think either of those things benefits you, but whatever.

[quartz needle]

k, ty

[quartz needle]

shouldn't it be -1?

because this says that p_j divides 1, no?

[unkempt void]

They subtracted p1... p_n from both sides of the definition of Q

[quartz needle]

i know

[unkempt void]

So why would it be - 1?

[quartz needle]

because it's p_j | Q

so Q - p_1 * p_2 ... p_n - 1= 0

[unkempt void]

Yes

[quartz needle]

i mean

same thing

[unkempt void]

I'm confused what the problem is

Ye

[quartz needle]

it just looks stupid

[iron surge]

this can be done by induction. Fix a,b, and m. Then induct on k

[quartz needle]

How do I know which Bezout's coefficients are desired?

[stiff rivet]

the question tells you: the ones computed by the euclidean algorithm

[quartz needle]

extended euclidean algorithm

extended euclidean algorithm just gives me any s_j and t_j

how do I know what j is desired?

[stiff rivet]

what

the algorithm terminates with bezout coefficients

[quartz needle]

?

my best guess is that i consider euclidean algorithm of a, b, and then add 1 to the j for which the euclidean algorithm ended

[stiff rivet]

what

the j is the number of steps, its entirely irrelevant

[quartz needle]

we consider
s_j and t_j

[stiff rivet]

yes?

[quartz needle]

j is the number of steps, its entirely irrelevant

[stiff rivet]

and at time of termination this is the output of the algorithm

[quartz needle]

whereas given j, we calculate s_j

[stiff rivet]

no

[quartz needle]

and s_j is bezout's coefficient of a

[quartz needle]

?

[stiff rivet]

you cannot calculate s_j from j

[quartz needle]

yes you can, becaue
s_j = s_(j-2) -q_(j-1) * s_(j-1), likewise for t_j

discord fucked up the formatting, and idk how to fix it

[stiff rivet]

indeed

you need $s_{j-2}$, $s_{j-1}$ and $q_{j-1}$

[sterile pumice]

Lochverstärker

[stiff rivet]

something along those lines anyway

[quartz needle]

but we know s_0 and s_1

[stiff rivet]

its not related to j

its just the results from the previous step(s)

[quartz needle]

how can it be not related to j and yet be the results from the previous step(s) (where j is a step)

[stiff rivet]

anyways, the algorithm terminates and then has computed the gcd and possible bezout coefficients

how is it related to j?

if i give you j = 10, this tells you nothing

[quartz needle]

no

i can calculate s_10

[stiff rivet]

the j is irrelevant, in fact the algorithm doesnt even keep track of it

[quartz needle]

given q

[quartz needle]

what do you mean by this anyways

[stiff rivet]

the algorithm terminates at some point

and at that point s_j and t_j are possible bezout coefficients

[quartz needle]

do you mean the successive steps that take s, and t, from s_0, s_1 and t_0, t_1, to s_j and t_j?

[stiff rivet]

what?

that's the algorithm

and it stops at some point and the last values it computed are the bezout coefficients

[quartz needle]

which are s_j and t_j, meaning that the algorithm does keep track of j

[stiff rivet]

it does not

look at a computer implementation

[quartz needle]

?

[stiff rivet]

it only keeps track of the variables that are required to calculate the next step

[quartz needle]

how does it know what's the last step?

if it doesn't take into account that the last step is the step that occurs after the last q

[stiff rivet]

when the remainder is 0

[quartz needle]

you mean that it takes the last step when the remainder is 0, or that the last step makes the remainder 0?

[stiff rivet]

the algorithm is over when it reaches a remainder of 0

and the last two computed values for s and t are then the bezout coefficients

it doesnt matter if it takes 10 or 10 million steps

[quartz needle]

we are going in circles

[stiff rivet]

because you refuse to accept my explanation

[quartz needle]

i had already accepted your explanation

that's why the circles

[quartz needle]

what does 'r' stand for?

[inner anchor]

Remainder

[quartz needle]

r_0 isn't a remainder

[inner anchor]

Other than r_0 and r_1 they are all remainders

I doubt another term exists for them

[quartz needle]

Isn't a^m + 1 a Mersenne prime, where m is a prime?
This wants me to show that a^m + 1 is a composite (e.g. not a prime) when m is odd (a number is odd when it's not divisible by 2, every prime with the exception of 2 is odd) - which would mean should this be true, a^m+1 isn't a prime for prime m

[inner anchor]

Mersenne primes are primes of the form 2^n-1

I dont really understand the rest of your argument

The statement that is to be proven is correct

[quartz needle]

nvm, i misread it

sorry

[bronze raven]

okay

so i constructed the multiplication tables for Z6

and i realise i have multiple answers for ii and iii

so im not sure if my ans is correct

this is the table

[light flicker]

Yes that's right

[bronze raven]

so theres actually multiple answers to the qn

[bronze raven]

is my presentation correct? or should i put the possible x values in a set or something

[bronze raven]

hello how to solve i?

[light flicker]

What are you confused about? @bronze raven

[bronze raven]

erm i know elements are referring to the numbers in Z6 right

like [1] [2] etc

i dont understand what it means by inverse under multiplication and their corresponding multiplication inverses

[light flicker]

Do you know what an inverse under multiplication is?

[bronze raven]

not really

[light flicker]

So I mean, in like the real numbers, 1/a is an inverse to a because if you multiply them together, you get 1

So it's the same thing here, an inverse under multiplication for n is something that multiplies n to get 1

[bronze raven]

ohh

so in this case its [1]?

the ans is just [1]?

1 * 1 = 1

[light flicker]

Not necessarily, it's asking for all the elements that have multiplicative inverses

[bronze raven]

so 5 x 5 as well?

theres only 2 from what i see

1 * 1 and 5 * 5

unless im missing out something

[light flicker]

Yeah, that's right

[bronze raven]

so the ans i will just write : [1], [5]

okay thanks

one last qn

i think this is false right?

[haughty lichen]

If no axiom of choice allowed yes

[bronze raven]

no axiom of choice allowed?

yes true? yes false?

[haughty lichen]

Any set can be well ordered if using axiom of choice

[bronze raven]

ok thanks

[stiff rivet]

you don't even need choice, just take your favorite bijection from Q \cap [0, 1] to N and use the order induced from N

(this question probably refers to the usual ordering though, in which cases this is not well ordered)

[faint basin]

Is there a procedure for finding n?

[light flicker]

let x be (a-b)/2pi. This is actually the same as finding a rational number close to x since if you have n/m that is close to x, then nx - m will be close to 0. So depending on what you know about a,b, there are many ways to find rationals close to it. Continued fractions is one way for example @faint basin

[sour karma]

does max{A,B} + c = max{A + c, B + c}?

[spare tangle]

I believe so

[polar ruin]

how did they go from 1 to 2?

[stiff rivet]

(7/4)^2 > (11/4)

and a^b*a^c = a^(b+c)

[polar ruin]

I mean how did he make (7/4)^k-2 (11/4) , (11/4) to (7/4)^2

[faint basin]

smaller than

not equal

[faint basin]

so it’s easy to see the than 7/4 squared is smaller than 11/4

[polar ruin]

Hmm isn’t 7/4 squared bigger than 11/4?

[stiff rivet]

yes, hence the RHS is greater than the LHS

if you multiply by a greater number, your result becomes greater

hence <

[polar ruin]

Ight

[faint basin]

tactical mistake by me 🤦‍♂️

[sage silo]

for which whole numbers is x^(3)-53 divisible by 3?

[light flicker]

@sage silo what have you tried?

[sage silo]

nothing

we havent learned about cubic congruences

[light flicker]

You don't really need to know anything about cubic congruences

How do you think you should start?

[sage silo]

add the 53?

x^3 congruent to 53(mod3)

ohh wait

how about i find a cubic number and can write the left side as x^3-c^3

x^3-3^3 is congruent to 26(mod3)

[light flicker]

Maybe think about simplifying 53 (mod 3)

[sage silo]

yeah

its the same as 2(mod3) right

or nah

-2(mod3)

[light flicker]

And -2 is the same as 1 mod 3

[sage silo]

yeah

ohh and now i can use fermats lil theorem right

nvm

yeah i dont see what i can do with x^3 congruent to 1(mod3)

i could write it as an equation in the right side

x^3-1=0(mod3)

and then solve it as an equation? is that it?

(x-1)(x^2+x+1)=0

my battery running out

fuck

[light flicker]

I mean, there are only three possible values of x(mod 3)

So you can just check all of these possible values to see which one works

[faint basin]

wait so find x close to m /n you mean

cuz if it's close to n/m then nx - m will not be close to 0

[light flicker]

Yeah you're right my bad

[sage silo]

How do i find en

Em

[light flicker]

Find what

[sage silo]

The 3 vues

Values

[light flicker]

There are only three possible values (mod 3), it's just 0,1 and 2

Everything else can be reduced to one of these three things

[sage silo]

Ohh

But theres gotta be the rest 1 too right

x^3=1(mod3)

[light flicker]

I'm not sure what you mean by that

[sage silo]

Ight bro

How do i solve

x^3=1(mod3)

I cant find any videos on it

Dawg you are so annoying

[stiff rivet]

[stiff rivet]

read that again

[sage silo]

One is a solution at least right

0 is congruent to mod 3

[stiff rivet]

yes

[stiff rivet]

?

[sage silo]

Whatev i gotta read up some more module

[wooden crater]

x can be one of the following forms : 3k, 3k+1, or 3k+2. cube each of those and see what happens to each result mod 3.

[noble anvil]

I've been working through a problem on Carmichael numbers, and I've been stuck on this part : $$n = p_1^{\alpha_1} \dots p_k^{\alpha_k} $$ such that $$p_1$$ is odd Let $$ w $$ be generator of $$ (\mathbb{F}_{p_1^{\alpha_1}},x)$$, We prove by the chinese remainder theorem that there exists t an integer such that $$ t = w [p_1^{\alpha_1}] $$ and for all other i, if it exists : $$ t = 1 [p_i^{\alpha_i}] $$ . Show that $$ t^{n-1} = 1 [n] $$

[sterile pumice]

Der Gegenstand ist einfach.

[noble anvil]

For all other i, I have t^(n-1) = 1 [p_i^{ alpha_i}]

and gcd(p_i^{alpha_i} , p_j^{alpha_j}) = 1 for all i != j

So I think I only have to show that w^(n-1) = 1

the thing is, w is a generator of $$ G = F_{p_1^{\alpha_1}} $$, so I know for sure that (if Phi is euler's totient function) w^{phi(n)} = 1

[sterile pumice]

Der Gegenstand ist einfach.
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[noble anvil]

so w^(n-1) = 1 probably isn't always since that would mean that phi(n) / n - 1 (which isn't the case so far..)

So I'm lost, what should I do ? A hint would be more than enough ^^

(Although I can say for sure that gcd(t,n) = 1)

[light flicker]

Is this assuming that the p_i are ordered? Like p_1 is the smallest?

[noble anvil]

nope

we just assume n has AT LEAST an odd factor

which we denote p_1

[light flicker]

Okay also wait, you write F_(p_1^a_1) but I feel like you mean Z/(p_1^a_1)Z?

[noble anvil]

there might be an even factor (i.e. 2) later

yes

I just saw that other notation being used

: )

oh yeah (F is for prime field)

excuse me, that was stupid of me..

[light flicker]

@noble anvil okay sorry I was in a seminar but I'm back now. But I don't see how this is true. Take like n = 6, then looking at the prime 3, 2 is a generator, but 2^(6-1) is not 1 (mod 3)

So that's why I think it might be necessary to assume that the p_i are in increasing order, in other words, that n is not even

[noble anvil]

that is what we want to prove in the end

(a priori n even, but we're supposed to deduce n even after.. Or so I think)

(it's okay btw)

in the question before this we showed that n is not a power of two

so n has an odd factor

which we note is p_1

[light flicker]

I mean, I don't see how you can deduce that n is not even since even n gives you a counterexample to the statement

[noble anvil]

I'll DM you the full problem (if you don't mind)

but anyways.. it's in the third subquestion

[light flicker]

Hmm

Yeah idk I'm a little confused too, but I think the point is that you're assuming that n is a Carmichael number. So by definition, that means that t^(n-1) = 1(mod n)

Although I guess you need to show that t is coprime to n but this is true

[noble anvil]

I feel so dumb rn

omg

just .. Aaaaaaarfh

ofc

n is a Carmichael number

WTF is wrong with me ?!!?!!!

[light flicker]

You're right that from this, you derive all the other properties

[bronze raven]

what does it mean state the reason clearly?

how do i do that

[sacred junco]

probably prove every step or something

[tranquil island]

Can anyone help ?

[light flicker]

@tranquil island what have you thought about?

[tranquil island]

bounding k^2/p by something but idk
Nothing helps

[light flicker]

It might help to realize the fractional part of k^2/p as something slightly more number theoretic

Or at least, think about what the numerator of the fractional part has to be

[tranquil island]

hmm
idk
does legendre's symbol help here ?

[light flicker]

it kinda does down the line

but take p = 13 or something

is there a nice way to find the numerator of the fractional part of 5^2/13

[tranquil island]

if p is 13 then k is between 1 and 6
we can just substitute and find the set then .. but how can this help

[light flicker]

I mean okay, how would you find the numerator of the fractional part of 5^2/13

[tranquil island]

by using the formula down below and rationalising

then you can see what the numerator is

[light flicker]

What formula down below are you talking about?

Oh

Okay my point is that

[tranquil island]

{x} =..

[light flicker]

If you're looking at 25/13 for example

to get the fractional part

you subtract 13 from the numerator

repeatedly, until you get something thats between 0 and 12

so in this case we would subtract it once and get 12/13

In other words, if we're trying to find the fractional part of k^2/p

We would look at the remainder of k^2 when we divide by p

[tranquil island]

yes and how can we find the remainder then

[light flicker]

What I'm trying to get you to realize, is that the numerator of the fractional part of k^2/p

is exactly k^2 (mod p)

[tranquil island]

hm yeah i see

[light flicker]

So now the question is just figuring out what the sum of

k^2 (mod p) for those values of k are

and then dividing this result by p

[tranquil island]

so we need to sum both side with sigme from k=1 to half p-1 ?

[astral osprey]

can you help me?

[tranquil island]

sigma

[astral osprey]

please

[tranquil island]

ok

[astral osprey]

please

[light flicker]

@astral osprey please read #❓how-to-get-help , this is not the right channel for this

@tranquil island yes thats right

[astral osprey]

you speak spanish?

[tranquil island]

hmm
aight

[astral osprey]

que canal me podrían ayudar en ese problema?

[light flicker]

Now we can apply all the quadratic residue stuff that we know

[tranquil island]

how

[astral osprey]

donde pongo ese ejercicio para que me ayuden?

[tranquil island]

And also where does the legenres symbol help

[light flicker]

@astral osprey Please read #❓how-to-get-help

I mean

the Legendre symbol is just a symbol

It can be used in the solution, but isn't really necessary

[tranquil island]

no envíe su ejercicio aquí, péguelo en el canal de álgebra, no aquí

[astral osprey]

oko

[sacred junco]

$(n+1)!/n(n+1\cdot{(n-1)!})=(n+1)!/(n+1)!=1$

[tranquil island]

ah

[sterile pumice]

Euclid

[sacred junco]

forgot parentheses

$\frac{(n+1)!}{n((n+1)\cdot{(n-1)!})}=(n+1)!/(n+1)!=1$

[light flicker]

Can we not do this here, we were trying to discuss a problem

[sterile pumice]

Euclid

[tranquil island]

and
k^2 = k^2 mod p
=> sigma k^2 = sigma k^2 mod 0
=> dividing both sides by p ?

[light flicker]

what

[tranquil island]

mod p*

I just wrote what you said

[light flicker]

I don't think you really understood what I said

[tranquil island]

:l

Could u write

[light flicker]

We're looking for $\sum_{k = 1}^{\frac{p-1}{2}} k^2 \pmod{p}$

[sterile pumice]

Zopherus

[light flicker]

But you need to be a bit careful

Because what we're doing is reducing each term, each k^2 (mod p) and then summing those up

We are not doing everything in mod p

[tranquil island]

set t = p-1/2
the sum is t(2t+1)(t+1)/6?

[light flicker]

No because you need to reduce each term (mod p) and then add them up

[tranquil island]

could you write your ideas
Cause somethings are unclear

[light flicker]

Maybe the notation is a bit unclear, but we're looking at the remainder of each k^2 when dividing by p

And then adding all of those up

[tranquil island]

yes and what are the remainders of k^2 when dividing by p
How can i know

[light flicker]

This is where you need to use ideas about quadratic residues

Each k^2 (mod p) is going to be some number that's a square mod p

[tranquil island]

Im not familiar with them , thats why im having trouble here

[tranquil island]

how can we find that "some number"

[light flicker]

I mean, it doesn't really matter

It's going to differ depending on k anyways, there's no nice formula for it

[tranquil island]

so lets just call it a

[light flicker]

You can't really do this problem without ideas about quadratic residues

[tranquil island]

i know that a is a quad resi if the equation x^2 = a mod p has a solution

[light flicker]

Yes

It might help to learn some more ideas about quadratic residues

You need to know a couple things to tackle this problem

[tranquil island]

tell me these things please

[light flicker]

I mean

I could

But I would just be giving you random facts that seem random

And you wouldn't really get a sense of how these facts fit into the wider framework and structure of quadratic residues

So I don't think it would really be beneficial

[tranquil island]

no
Juat give them to me
Everything you know about them

and i will try to demonstrate all of them to understand

[light flicker]

I think it would just be best for you to pick up a textbook and read the sections on quadratic residues, Silvermans a friendly introduction to number theory would be a good choice

[tranquil island]

ah alright thanks

[urban peak]

how can i show that for for A_n, n naturals and prime p, (A_1+A_2+...+A_n)^p \equiv A^p_1+A^p_2+...+A^p_n mod p?

[light flicker]

Show it for n = 2 and induct

[urban peak]

theres no shortcut? thought since it seemed like sum version of fermats little theorem there would be but idk

[light flicker]

I'm not really sure what you mean by shortcut

You don't need Fermat's little theorem at all

[unkempt void]

could just use multinomial expansion i guess

but i'm sceptical that has any advantage over just what zopherus suggested, especially as you'd probably have to prove the validity of the expansion anyway

[brisk shard]

Is there some theorem that states that (x + 1)ⁿ ≡ nx + 1 (mod x²)?

[light flicker]

The binomial theorem?

[brisk shard]

Ahh, OK. Thanks.

[sacred junco]

Viable (but not sure if optimal) algo for root finding mod n with factorization of n known

1. Cantor-Zassenhaus your polynomial to quickly get your roots mod each of the distinct primes in n
2. Hensel's lemma go brrrr lift them roots to the right power uwu
3. CRT permuting an ordered set of roots baby WOOO THATS WHAT IM TALKIN ABOUT

[fossil quiver]

Do you think that exist some suffiently large even integer can be written as sum of two prime numbers?

It's like Vinogradov's theorem, but for Goldbach's strong conjecture

[light flicker]

What if the polynomial doesn't have a simple root mod p? Then you can't lift that root using hensels

[viral breach]

They've written in a very confusing language

The domain, the range. It's very very confusing to read. I know the whole concept but trying to understand the text.

[sacred junco]

What is a simple root? @light flicker

[light flicker]

Multiplicity 1

[sacred junco]

Wait fr?

[light flicker]

If f factors as (x-1)^2 then 1 is a double root and not simple

Yes hensels can fail in these situations

[sacred junco]

Wait I was kinda assuming the polynomial is squarefree anyway cause Cantor-Zassenhaus requires that

But disregarding that I'm still curious wait why would Hensels lemma fail there

Cause the derivative becomes 0 doesn't it fuuuuuck

[light flicker]

Yeah

[sacred junco]

Nice

[light flicker]

How do you think of hensels lemma? Or like how do you think about the reason it works

[sacred junco]

A messy proof that I don't remember that was more arithmetic than intuitive
Ik it is literally Newton's method in the p-adics and that is really cool but not sure how to make the connection back to root lifting

The messy proof was in a number theory class and it was just mod arithmetic but long-winded

[light flicker]

Yeah that's a good intuition, but yeah newton's method requires division by the derivative. So that fails if the derivative is zero

[sacred junco]

Right ahhh nice

[light flicker]

An example is looking at x^3 + 3x + 9 mod powers of 5

It's roots are 3 and 4, but it has a double root at 3 when you look mod 5

When you try to lift these to solutions mod 25, you'll see that there's only one solution

In other words, only 4 lifts to a solution mod 25, 3 doesn't

[sacred junco]

Dang makes sense

[sacred junco]

I'm gonna code what still works up and have some fun getting some sequences generalizing automorphic numbers :)
x^n-x =x(x-1)(cyclotomic boi) is a product of distinct irreducibles so I think I'm good? Not sure how to prove that the cyclotomic part never becomes x or x-1 mod some p tho

https://math.stackexchange.com/questions/305111/irreducible-cyclotomic-polynomial
Huh Jesus Christ I will read this
Apparently p just needs to be a primitive root mod the "index number" of each cyclotomic factor

Fuck it I'm lazy not reading just gonna implement it LOL

[sacred junco]

Well it's definitely gonna fail a lot mod 2 cause phi_2(x) = x+1 hows up as a factor quite a lot, whenever n-1 is even lmao

[light flicker]

I'm pretty sure that an irreducible polynomial f will only have multiple roots mod p if p divides the discriminant of f

Yeah this is true, and you don't even need the irreducible condition @sacred junco

[sacred junco]

That's super mysterious to me but very nice

[light flicker]

It's not too mysterious if you know the definition of discriminant

Like if you have a polynomial f that's not square free, then the discriminant of f is zero

[sacred junco]

Not familiar with general polynomial discriminants or their motivation tbh. But luckily there's a nice formula for $disc(x^n-x)$
I have just been testing out case by case but I would conjecture it's $(-1)^{\lfloor \frac{n+2}{2}\rfloor}(n-1)^{n-1}$

[sterile pumice]

zd

[sacred junco]

Instead of rambling on here I will post my lil thing when it works xD or screenshots

[light flicker]

I'm not so sure this works exactly but it looks close. Look up the discriminants for cyclotomic polynomials

[sacred junco]

Basically it should construct the n-morphic numbers mod 10^k with some exception given by the discriminant thing

[sacred junco]

Truuu there's some kind of product property I could combine that with x times a product of cyclotomics right

[light flicker]

Yeah

[sacred junco]

Oh god the product property needs the resultant
Time to see how this Sylvester matrix shit work

Oo but resultants "factor" in the first argument so it won't be that bad

[next thunder]

I am trying to prove that GCD(m,n) = 1 when m!+1 = n^2. I have managed to prove that n is always odd, but that's about it.

[sacred junco]

hint: ||lemma named after some french dude||

[next thunder]

n seems to be a prime number, but I can't say that with much confidence. n is always greater than m and so being able to prove that n is prime would be a way to prove this

[sacred junco]

one of the more important results in elementary number theory involving gcd

Basically, you don't need to worry about solving the diophantine equation m!+1 = n^2 because there's probably a lemma in your toolkit that already tells you why gcd(m,n) = 1 always @next thunder

Although solving that would be interesting I don't know how to do it, not great at problem solving lololol

yeah I see what you mean about the primes the only solutions (m, n) that are reasonably computable by bruteforcing this are (4, 5) (5, 11) and (7, 71) n is prime every time

I would guess that solving this comprehensively, if that is what your next step or aim is, would involve looking at bounds for m based on the greatest power of 2 in m! and then maybe one would be able to suss out the distance to the closest perfect square? idk this looks like some competition math shit you would find on Michael Penn's channel, I'm not great at this stuff

@next thunder sorry I got sidetracked lmao are you trying to solve the equation as well or just trying to prove that gcd(m,n) is 1? if the latter here ||https://en.wikipedia.org/wiki/Bézout's_identity||

As for the actual equation... WAIT LMAO it's an unsolved problem: https://en.wikipedia.org/wiki/Brocard's_problem, that's cool.

finite number of solutions would be an abc conjecture corollary apparently

[next thunder]

well excuse my language but what the hell, nice homeworks you've given us teacher

I've been looking at bezouts identity but it's still new to me and I can't see a clear connection here

[sacred junco]

Bezouts lemma just says that if two numbers are made out of the same size blocks then no matter how many of those numbers you shove together, the result is also made out of the same size blocks.
So like 15 and 6 are made up of threes since that's their gcd, any linear combination of 15 and 6 will be divisible by 3

[next thunder]

yeah I had to prove that a bit earlier and I think I got it right.I've also figured out that gcd can't be even, but can't get further than that

[sacred junco]

The great thing about Bezout is that you can look at literally any linear combination and be like
vw+xy = z ok z is a multiple of the gcd(v,x). It's also a multiple of gcd(v,y), and of gcd(w,x) and of gcd(w,y)

And if z has only a few factors, then you know what the gcd has to be since that thing which is only made of a few factors is a multiple of the gcd

so that means the gcd has to be one of those factors

[sacred junco]

Basically if you see anything in the form of a linear combination, you just got a crapton of extra information about what you're working with, it's great
So applying this in your case
n^2 - m! = 1
Can you write the lefthand side as a linear combination of m and n?

[next thunder]

if GCD(a,b)= ax +by then GCD(b,y) = 1. So if I can substitute x to be the equation for m and y the equation for n, then that could be one way of approaching this problem

[sacred junco]

Wait, GCD(b,y)=1? that's not necessarily true

[next thunder]

hmm the version of this theorem in my course materials says that if GCD(a,b)=ax+by for some x and y in Z then GCD x,y = 1

[sacred junco]

well yeah actually that is exactly what you need but that doesn't correspond to gcd(b,y) in what you wrote up there but anyway

[sacred junco]

so ignore that and just go on this idea cause this is good

err wait sorry, it's even simpler than that. It's that if ax+by = 1, then GCD(a,b) has to be 1 (and gcd(a,y), gcd(x,b), and gcd(x,y)) because 1 is a multiple of GCD(a,b), but the only positive factors of 1 are... 1.

So if ax+by = 1 means gcd(a,b)=1, what does this imply about
n^2 - m! = n(n) + m(-(m-1)!) = 1?

[next thunder]

I feel like I should find numbers a and b for which GCD(a,b)= a* (n^2)/(m-1) + b* sqrt(m!+1) is true. But this isn't easy

[next thunder]

How did you get this? n^2-m! is 1 but n(n)+m... bit is not something that I can connect to anything

[sacred junco]

m! = m(m-1)! right?

[next thunder]

ah yeah that's how you got it

[sacred junco]

yeah I was just writing 1 = n^2-m! in the form of a linear combination :^)

[sacred junco]

I can hop into voice to explain better if u like

[next thunder]

I think I've got this, now if I can just show that GCD(n, (m-1)!) = 1 then this is done

well perhaps not, (m-1)! and n are pretty much guaranteed to have a GCD other than 1

[sacred junco]

You already have that gcd(n, m) = 1 since you know
1 = n(something) + m(something)

And the left side has to be a multiple of the gcd, but 1 only has 1 as a factor so gcd(n,m)=1

[next thunder]

I think I got it, thanks for your help

I posted a premium quality cat pic of my own taking into the cats channel, I hope it warms your hearth

[sacred junco]

it is a good cat

[urban peak]

what is a torsion collection? textbook im reading just talks about torsion collection in some theorem, but it never showed what it meant. my algebra knowledge is limited so all of the ones i found online are too complicated

[light flicker]

What's the context?

[urban peak]

elliptic curve

[light flicker]

Any more context? I've never heard of this term in relation to elliptic curves before

Torsion points are super important but I'm not sure what exactly they mean by collection

[urban peak]

it is talking about Mazur's theorem which i cant seem to find much about online

It also mentions the Nagell-Lutz theorem which seems simpler

[light flicker]

https://en.m.wikipedia.org/wiki/Torsion_conjecture

Look at the elliptic curve case here, that's mazurs theorem

I assume torsion collection just means the collection of torsion points

[urban peak]

oh yeah you are right ty 👍

[somber lagoon]

How to prove this?

[dawn lily]

I'm not 100% sure my proof is correct, but I did something like this:
Assume that $2^n-2=2(2^{n-1}-1) = np$, for prime p; then either $p=2$ or n is even.
Case 1: p=2: then $2^{n-1} = n+1$, and by noticing that both functions are strictly increasing, intersect at n=3 and $$2^{4-1}=8>4+1$$, we conclude that for $n>=4$ there are no solutions here.

Case 2: n is even: Let $n=2k$; then $2^{2k-1}-1=kp$, for $p>2$. Notice that k must be odd. Reducing mod k, we get $2^{2k-1}-1=0\pmod{k}$. Notice again that since k is odd, 2 and k are coprime and hence Euler's theorem applies, so $2^{\varphi(k)}=1 =2^{2k-1}\pmod{k}$ (where phi is Euler's totient function). For all $n\in\mathbb{N}$, we have that $\varphi(n)\le n-1$, which implies that $2k-1\le k-1$, so k is either two or 1 - it can't be two because it's odd, and it can't be 1 because $n\ge 4$, thus there are no solutions here too.

[sterile pumice]

Dol∞v

[somber lagoon]

Thank you very much. But I don’t get the third line from bottom to top since all I got is that the order of 2 in Z/kZ divides both φ(k) and 2k-1

[dawn lily]

oh yeah, you're right, my bad. I'll try to modify the proof later.

[dawn lily]

I couldn't really finish the proof myself, but I found a solution here: https://artofproblemsolving.com/community/c6t177f6h2669914_a_simpe_problem

[somber lagoon]

Thank you so much for finding it, I understand it now.

[livid raven]

c is not 1 or -1 mod n, and (c-1)(c+1) = 0 mod n, why is gcd(c-1,n) a non-trivial divisor of n?

[stiff rivet]

what have you tried?

[livid raven]

I might need some hints, I really dont know.

Maybe I even gave too little context. The book states it like its trivial..

all I could conclude is gcd(c,n)=1, since c^2 = 1 and c*c = 1 inveerse exist

but not why gcd(c-1,n) is not equal to +-1 +-n

[light flicker]

if gcd(c-1,n) was equal to n, then you must have that c-1 divides n. Can you see why this can't happen?

[livid raven]

I played around there but I failed: gcd(c-1,n)=n, then n|(c-1) and n|n. and we know n|(c-1)(c+1) but I see no problem here.

[light flicker]

oops yeah, I mean that n divides c-1

Can you rephrase n dividing c - 1 in terms of mod?

[livid raven]

n k1= (c-1), n k2= (c-1)(c+1) ?

c-1 = 0 mod n?

[stiff rivet]

which turns into c = 1 mod n (which is wrong by assumption)

so n does not divide c-1, similar argument works for c+1, but n does divide (c-1)(c+1)

[livid raven]

Oh..

Im blind.

[sterile pumice]

buckman78

[light flicker]

@gleaming juniper how do you know that n= 1 or n= 2^n - 2?

[gleaming juniper]

I was thinking about the definition of prime number. The only positive divisors of a prime number are 1 or itself. Thoughts?

[light flicker]

2^n - 2 is not prime

[gleaming juniper]

ok. I'll remove it.

[vocal totem]

Isn’t that number even?

[quick furnace]

alright i have this modular arithmetic BS that i'm having an unreasonably hard time with

i have a number q between 0 and 10^n - 1 such that q^2 = q mod 10^n. there exists d in {0,1,...,9} such that q^2 = d*10^n + q mod 10^{n+1}

apparently the number q' = (10-d)*10^n + q satisfies q'^2 = q' mod 10^{n+1}???

but i for some reason am having trouble actually establishing that symbolically

like, expanding [(10-d)*10^n + q]^2 leads me nowhere

if it matters, q ends in 6

ping me if replying

[wise oyster]

It works when I expand it out?

Wait nvm

It works if we had q^2 = d10^n * q + q mod 10^(n+1) since we have [(10-d)10^n + q]^2 = (10-d)^210^2n + q^2 + 2(10-d)10^nq = d10^n* q+ q -2d10^nq =q-d10^n*q = q’ mod 10^(n+1) but yeah that obviously won’t help

Oh fuck I’m so not bothered to slash all my asterisks

[wise oyster]

Yeah idk I’ve been transitioning between a bunch of equivalent forms but I don’t quite get the conclusion

[pliant citrus]

I’m trying to prove m+n=101 where gcd(m,n)=3 and wanted to make sure my proof was correct. I said assume there exists m,n integers such that their sum is 101. 3|m and 3|n so n=3c m=3k for c k integer then 3c+3k=101 so c+k=101/3. Contradiction since sum of integers cannot be rational. Does this sound sensible?

[light flicker]

yes

[pliant citrus]

Awesome thanks

[jovial wigeon]

what does '|' mean in 'n|(2^n-2)'

[viscid wave]

n is a factor of (2^n-2)

In other words, (2^n-2)/n is an integer

[jovial wigeon]

thanks

[fresh hound]

how can i show that $p_{n+1} \leq p_{n}^{2}$ where $p_n$ corresponds to the nth prime number

[sterile pumice]

beachcow

[fresh hound]

or is it even necessarily a true statement

[light flicker]

This is true by Bertrand's postulate for example

I don't know if there's any easier way other than going through Bertrand's postulate, which implies that p_{n+1} \leq 2 p_n

[fresh hound]

hmm

Ok i was trying to prove a different statement related to this that required induction and ended up stuck at that point

it was that $p_n \leq 2^{2^{n-1}}$

[sterile pumice]

beachcow

[fresh hound]

and i tried strong and weak induction

and got to the point where i said $p_{k+1} \leq (2^{2^{k-1}})^2$

[sterile pumice]

beachcow

[light flicker]

For this, you should look to show that p_{n+1} \leq p_1 p_2 ... p_n + 1

[fresh hound]

which is less than or equal to (p_k)^2 by induction hyp

[light flicker]

and to do that, you should think about Euclid's proof of the infinitude of primes

[fresh hound]

Ah i see

thanks

[light flicker]

this is written up in Ireland and Rosen's number theory book in chapter 2 section 4 too if you want to read that

[quick furnace]

im still reeling from this bullshit

because it appears to work yet defies all explanation

at least in the case that im looking at

[jolly frigate]

Proof that if a^2 is divisible by 7 than a is also divisible by 7

[inner anchor]

euclids lemma

[unkempt void]

In this special case I'd prove the contrapositive: if a isn't divisible by 7, neither is a^2

Write a = 7q + r for 0<r < 7

[latent hare]

@quick furnace does q have to end in 6? Because a counterexample can be taken with q=25

[quick furnace]

the q's for which i tried this all ended in 6

so maybe yes that does matter

[stiff rivet]

thought i solved it, but there is still some issue with it, so i don't feel like i wasted my time here is what i wrote up:

First notice that $q \equiv 6 \pmod{10}$ implies $q \equiv 1 \pmod{5}$ and $q \equiv 0 \pmod{2}$. Further recall that the Chinese Remainder Theorem gives you an isomorphism
$$ \phi\colon\bZ/10^n\bZ \to \bZ/2^n\bZ \times \bZ/5^n\bZ \text{.}$$
Now the polynomial $X^2 - X$ has two roots in $\bZ/2\bZ$ resp. $\bZ/5\bZ$, namely $0$ and $1$. Those lift uniquely to $\bZ/2^n\bZ$ resp. $\bZ/5^n\bZ$ for any $n \in \bN$. It follows that $X^2 \equiv X \pmod{10^n}$ has precisely $4$ solutions, namely the preimages of $(0, 0), (0, 1), (1, 0)$ and $(1, 1)$ under $\phi$.
The assumptions imply that $q$ is the preimage of $(0, 1)$.
Now there actually is an explicit description of the map $\phi^{-1}$ using Bézout's Lemma, which shows that the nontrivial solutions of $X^2 \equiv X \pmod{10^n}$ are of the form $k2^n$, $\ell 5^n$ with $k, \ell \in \bZ$ such that $k2^n + \ell 5^n = 1$. The solution that is equivalent to $6$ modulo $10$ is the one of the form $k2^n$.

[sterile pumice]

Lochverstärker

[stiff rivet]

given this description of $\phi^{-1}$ it would suffice to show that $\frac{q'}{2^{n+1}}$ is a possible bezout coefficient of $2^{n+1}$, but i could only show it is an integer 🤷

[sterile pumice]

Lochverstärker

[stiff rivet]

there is probably an easier way but this is what i tried @quick furnace

[fresh hound]

prove if n>1 is not prime and p does not divide n for all p \leq cube root of n, then n is the product of two primes

i only know that if n>1 and p does not divide n for all p \leq sqrt(n), then n is prime

[light flicker]

Do you understand the proof of this fact?

[fresh hound]

i proved that first by justifying that all divisors of n must be less than or equal to sqrt(n)

and n must have a prime factorization composed of numbers less than sqrt(n), unless it is prime

so if no p divides n, then n must be prime

[light flicker]

How did you justify this?

[fresh hound]

if the divisor of n is greater than or equal to sqrt(n), then the quotient of n with the divisor must be less than or equal to n/sqrt(n) which is sqrt(n)

[light flicker]

okay so can you extend that idea?

instead of looking at the product of 2 things to get n, what if we look at the product of 3 things to get n, what bounds do we get then?

[fresh hound]

@light flicker so I let n = abc this time and let bc be greater or equal to n^(2/3). then used to the same argument to arrive at the conclusion that a must be less or equat to n^(1/3)

but if there are no p \leq to n^(1/3) that divide n, then what does that mean about n

it is supposed that n is not prime

[languid latch]

are thse elementary

[gaunt wing]

'

how should i even approach this?

[inner anchor]

I think you have the problem statement wrong. As is, 11 is a counterexample. I would expect it to say that n is the product of at most 2 primes

[lone goblet]

isn't this from Project Euler? Looks like a hard problem, maybe I'll try it. Do you have the problem number?

[rugged moth]

can anyone point me some papers/books where I can learn how to solve system of linear equations in Zn, where n is not necessary prime

[light flicker]

@rugged moth Take a look at chapter 3/4 of Ireland Rosen

[rugged moth]

@light flicker cn u share the full name of the book? will be easier to find that way, thnx

[light flicker]

A Classical Introduction to Modern Number Theory by Ireland and Rosen

[lusty perch]

Suppose we have a set {0,…, n-1}
And for two elements a,b
we define a binary operation (a + b) mod n
Is this associative for all n? My intuition says it is, but I’m struggling to write down a rigorous proof.

[light flicker]

I think you can just show that both things are equal to (a + b + c) (mod n)

[lusty perch]

I’ll try to do that then ty

[upbeat wren]

It has to do with the fact that 7 is a special number.

oops didn't scroll down to the end.

[crisp cape]

<@&268886789983436800> this is a scam

[sacred junco]

n!+k , 2≤k≤n for large n s

bruh moment

[trim heron]

is the difference between interger multiples of the same irrational number always irrational, always rational, neither? (disregarding the trivial case where both multiples are equivalent)

Like $a\cdot \sqrt(2)-b\cdot \sqrt(2)$

[sterile pumice]

Dpao

[trim heron]

Id think that linear combinations--which encompasses their difference--of the same irrational number with nonequal rational scalars should always irrational since you can factor out an irrational, and get a rational (sum/difference of two rationals is rational) times an irrational number

[weary sundial]

I'd think always irrational for this question? (Except for when a=b as you say)

Linear combinations are a lot more than integer multiples so I'm not sure why you bring them up

By the way you probably want to write it as $a\sqrt{2}-b\sqrt{2}$

[sterile pumice]

ShatteredSunlight

[stiff rivet]

this is just $\sqrt{2}(a-b)$ which is irrational for $a-b$ a nonzero integer

[sterile pumice]

Lochverstärker

[stiff rivet]

(in fact it's irrational for a-b a nonzero rational number)

[sacred junco]

What's the relation between Fibonnaci and Jacobsthal numbers

[brisk shard]

Is there some way to check whether a number is squarefree that's easier than factoring?

[light flicker]

https://projecteuclid.org/journals/duke-mathematical-journal/volume-164/issue-2/Detecting-squarefree-numbers/10.1215/00127094-2856619.short

there are (conjecturally) ways to do it without factoring

But it depends what you mean by easier I guess

There are no known polynomial time algorithms

[brisk shard]

Thanks!

[frozen pebble]

Could someone show how to prove g(n,k) = g(n-1, k-1) + g(n-k,k) for 0 < k ≤ n using a bijection?

g(n,k) = # of partitions of n into k parts

[sterile pumice]

marc

[frozen pebble]

[light flicker]

@frozen pebble what have you tried?

@dapper sluice you can just directly prove it by solving that equation at the end for x

[grave carbon]

I am trying to manipulate $$\frac{1}{(1-z^3)(1-z^4)(1-z^5)}$$ to get it into the form $$\frac{Q(z)}{(1-z)(1-z^p)^d}$$ but I'm having trouble with the algebra. Is someone able to help me on this?

[sterile pumice]

beeswax

[grave carbon]

Q(z) is just some polynomial in z

[tawdry spear]

f(x)

[pliant citrus]

Trying to prove if a=b mod n then a^m = b^m mod n for all m natural. Did proof by induction. Base case, m=1 true by hypothesis. Inductive step assume it true for some n natural. So we have a^m=b^m mod n. Then a^m*a=b^m * b mod n so a^m+1= b^m+1 mod n. Not sure if this is correct, but think I’m mostly hung up on the multiplication of the two congruences. Does it look ok?

[pliant citrus]

Any thoughts?

[light flicker]

@pliant citrus That's correct

[pliant citrus]

Awesome, appreciate it 🤝🤝

[sacred junco]

Hi, I have one question

I need to prove that if $m+n$ is odd, then $m-n$ is odd, without bearing in mind that $m$ and $n$ are both odd or even

[sterile pumice]

xd nope

[inner anchor]

Look at their sum

[sacred junco]

The sum is $m+n = 2s$ where $s\in\mathbb{N}$

[sterile pumice]

xd nope

[sacred junco]

But from here idk what to do, because if I have that $m = 2s-n$, then idk because I can't use that $m,n$ are odd

[sterile pumice]

xd nope

[inner anchor]

I mean look at (m+n)+(m-n)

[sacred junco]

Oh

[stiff rivet]

using induction

[sacred junco]

If a,b are positive integers, prove that a+b+lcm(a,b) is not a power of two.

[olive raptor]

gcd(a, b) = d
a = ds, b = dt where gcd(s, t) = 1
lcm(a, b) = dst
a + b + lcm(a, b) = d(s + t + st) = 2^n
d = 2^a, s + t + st = 2^b ==> b > 0 ==> s + t + st even ==> (s + 1)(t + 1) odd
hence, s and t are both even, but gcd(s, t) = 1, so contradiction

[sacred junco]

Thanks

[subtle cairn]

does someone knows if this is true?

x,y being integer numbers

or which theorems do i need?

[light flicker]

Bezout's lemma

[subtle cairn]

how do the exponents affect the question?

[light flicker]

not much

[subtle cairn]

ok

and that lemma applies to numbers that are not relative primes?

like in this case?

[light flicker]

I think you can answer this question just by googling Bezout's lemma and reading the statement

[subtle cairn]

ok

[urban peak]

is it ok to ask a question about generating functions here? combinatorial structures channel seems too sophisticated

[unkempt void]

discrete may be a better fit?

depends what kind of generating functions we're talking i guess aha

[urban peak]

ill just write it here and move it if i need : Have a sequence $a_n={N\choose n}{M\choose 0}+{N\choose {n-1}}{M\choose 1}+{N\choose {n-2}}{M\choose 2}\ldots +{N\choose 0}{M\choose n}$. WTS (1+x)^N(1+x)^M is the generating function for a_n

[sterile pumice]

kingphilip77
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[urban peak]

feel like it should be simple just nothing really working out

[light flicker]

You just use the binomial theorem and multiply it out?

[chrome bluff]

Is there a different way of writing $i_{k+1 \mod m}$ w/o having that long subscript?

[sterile pumice]

dackid

[empty falcon]

ive got no idea where to put this but i got an idea that id like to hammer out that has to do with the lucas numbers pascals triangle and f(x,y,n) = x^n + y^n
if anyone would like to discuss this new idea in mathematics voice, @ me
I'd love to iron it out with a second perspective

[quartz needle]

How did he get this from knowing that X8Y8 is divisible by 11?

only 1,3 make sense (since they are equivalent to each other)

as the rule of divisibility by 11 is 11|sum of digits at even places - sum of digits at odd places

@scarlet geode

[scarlet geode]

I don't understand the question

I hawe no idea what x8y8 is

[quartz needle]

the point is to calculate the highest and the lowest number of the type of X8Y8 such that it is divisible by 11, as well as the number of such numbers

[scarlet geode]

I cannot understand what X8Y8 is

[quartz needle]

x, y are digits

[scarlet geode]

Oh

I also have zero context to be able to understand teh image

You haven't sufficiently explained it

What does that even pertain to, what is trying to be said about these equations

Is it saying one of the four must be true?

[quartz needle]

that's all it says, you are given the rule for the divisibility of 11 and are asked to calculate the number of numbers of the form X8Y8 such that they are divisible by 11, as well as the highest and the smallest of such numbers

that pic is his answer to the question, he doesn't explain the logic

just says that k is either 0 or 1

[scarlet geode]

You are not reading what i'm asking

[quartz needle]

pertain to
The question:
you are given the rule for the divisibility of 11 and are asked to calculate the number of numbers of the form X8Y8 such that they are divisible by 11, as well as the highest and the smallest of such numbers

Is it saying one of the four must be true?
yes

My answer is
11|(x+y-16) but this doesn't satisfy the case
x + y = 5, and thus provides an incorrect answer

I'm hoping that you'd solve this question, and explain to me the reasoning for why he considers
(8+8)-(x+y) = 0
and
(8+8)-(x+y) = 11
in spite of the fact that the rule of the divisibility states that a number is divisible by 11 when the result of the subtraction of the sum of the digits at odd places from the sum of the digits at even places (thus x+y-16) is divisible by 11

occupied

alright, nevermind

[rain mountain]

can someone help

[light flicker]

@rain mountain what exactly do you need help with?

[rain mountain]

wait i sent the wrong thing

but i was iffy about that

does my proof for that work?

[light flicker]

Yes that works

[rain mountain]

this is what i meant to send

im not sure exaclty where to start-- i first said if (a, b) = c then (a, b)^n = c^n by substitution

[light flicker]

Yeah, so show that (a^n, b^n) = c^n

[rain mountain]

through..?

[light flicker]

I mean, you can show that c^n divides the gcd

[rain mountain]

uh

would i use induction at all

maybe

[light flicker]

you don't need to and I don't think it'd help

[rain mountain]

what would you do then

[light flicker]

did you do what I suggested?

[rain mountain]

no like how would i show that

im kinda lost

[light flicker]

Do it just like what you did for the other problem

[rain mountain]

oh

then we can prove that c^n = (a^n, b^n) because e and d are relatively prime, hence e^n and d^n as well

?

[light flicker]

yes exactly

[hallow halo]

yo lets go number theoryy

[hallow halo]

how does one get access to the advanced channels

[stiff rivet]

#get-advanced-access

[hallow halo]

i added the roles but dont have access still

[stiff rivet]

read it again, this time everything

[empty falcon]

how would i go about proving that

has no integer solutions when x, y, and a are Natural numbers > 0

how would i even go about proving it for a = 1?

[hallow halo]

use modular

[empty falcon]

right but howwwwwww

im not too experienced with modular

i can make some basic statements about the equation bu then i run into walls

[hybrid lodge]

Fermats last theorem

U can use that

(x+y-3a)³=x³+y³ if u solve it. This cant be true at all

[empty falcon]

well you see
i was trying to use this to prove fermats last theorem in a sence

[empty falcon]

how would i prove it without that

@hybrid lodge

[hybrid lodge]

Don't know 😅

[grave carbon]

If a=b, what is min(a,b)?

[stiff rivet]

a=b

[grave carbon]

So, if I'm trying to apply
$$ \sum_{a,b \geq 0} z_{1}^az_{2}^b = \sum_{a \geq 0} \sum_{b \geq 0}z_{1}^az_{2}^b $$
to something like
$$ \sum_{a,b \geq 0} \min(a,b)z_{1}^az_{2}^b$$, would it be necessary to do cases?

[sterile pumice]

beeswax

[grave carbon]

for a>b, b>a, a=b?

[stiff rivet]

you can split this sum into two, one over a, b >= 0 with a >= b and one with a, b >= 0 with a < b if you want ...

[grave carbon]

So like [sum 1 with a<b] + [sum 2 with a>=b] ?

[stiff rivet]

yes

[grave carbon]

Ahh thank you. In general, would this way be more efficient than listing the cases?

[stiff rivet]

it depends

[pliant citrus]

I’m trying to figure out some stuff about relation ~ on Z where x~y is x^3 = y^3 mod 4

First I want to show its an equivalence relation which is basically by definition I think. Reflexivity, is obvious. Symmetry is properly of congruence. Transitivity once again property of congruence. If this sounds wrong please correct me

But I’m trying to find the number of equivalence classes and describe each one which I am having trouble with

Any advice on how to find equivalence classes?

[dusk heath]

pick a number x in Z

what are the possible values of x^3 mod 4 ?

A "more abstract" hint would be: ||This equivalence relation is a refinement of the equivalence relation x ~ y <=> x = y mod 4, so you already know there can only be atmost 4 classes||

[thorn wedge]

Hello, I have seen many people reason the equation a = bc, where gcd(a,c) = 1 like this: since gcd(a,c)= 1, then it means a|b. My question is, why do they reason in this way? Is this from the Euclid's Lemma: if a|bc, and gcd(a,c)=1, then a|b. So in this case, a=bc means a|bc, then we can apply Euclid's Lemma?

[stiff rivet]

🤔

if a = bc and gcd(a, c) = 1, then c=1 and b=a

i guess you mean a | bc?

in this case you argue via the fundamental theorem of arithmetic

euclid is only formulated for primes

i guess you can inductively use euclid on the prime divisors of a

[thorn wedge]

I usually do this reasoning

But I've seen people do the other one I mentioned. Just wondering what their reasoning was. I'm waiting for one of their replies, hope they'll explain

[inland birch]

why is 3^-1=4(mod 11) ?

[swift shard]

Because 3×4 = 1 (mod 11)

@inland birch

[inland birch]

thanks

[quartz needle]

Find a perfect number that is divisible by 6 and has exactly 6 factors.
4k = 1 + 2 + 4 + x + y + z
what do I do now?

[quartz needle]

Find all non-negative integers such that the sum of their product and quotient is equal to 185.
xy + x/y = 185
what now?

[quartz needle]

Show that if k,n, are different integers, then the number 2n(n-5)-(n-k)(n+k)-5n(2k/5 -2) is divisible by k-n
upon expansion
k^2 -2nk +5n
what do I do now?

[sacred junco]

Just a question about definitions I'm not sure. Perfect squares are just squares of natural numbers right? I mean, are a^4, a^6, a^2k in general for a,k in the positive integers also perfect squares?

[stiff rivet]

$a^{2k} = (a^k)^2$

[sterile pumice]

Lochverstärker

[quartz needle]

@stiff rivet could you please help me, too?

[quartz needle]

The hundreds and ones of the three-digit number n are odd numbers. Writing the digits of the number n in reverse order gives the three-digit number k. Prove that the number n-k is divisible by 198
n = (2a-1)X(2b-1)
k = (2b-1)X(2a-1)
necessarily, 2a-1 > 2b -1
n - k = (2a-2b-1)9(2b-2a+10)
2 a - 1 = 9 v 7 v 5 v 3 -> a = 5 v 4 v 3 v 2
2b - 1 = 7 v 5 v 3 v 1 -> b = 4 v 3 v 2 v 1

e.g.
for a = 3, b = 1
n-k = 399
which means that I have fucked up?