elementary-number-theory

[silk vine]

I'm still studying differential equations and series.

And other stuff like statistics.

It's gonna be a while until I study these topics.

I've only heard about the bears tho.

lol

[sacred junco]

https://math.stackexchange.com/a/145348/476484

the Bernstein article seemed too convoluted

[silk vine]

I'll take a look at both anyway. Thanks a lot.

[sacred junco]

can you use fundamental theorem of arithmetic ?

oof

I guess your best bet would be to show that two numbers have same divisors so they must be equal

well, it's really easy to take gcd/lcm with numbers expanded into a product of primes

it boils down to max/min of their powers

so it would just be a property of max/min

of numbers

did you have a proof of ab = gcd(a, b)lcm(a, b) ?

analyse it, this should be similar

abc = dN where N = lcm(ab, ac, bc) (because from definition, N|abc)

we want to prove that d = gcd(a, b, c)

hmm?

no we can't

N = kab = lac = mbc for some k,l, m

yeah, just follow the proof

that's how you prove that d is a common divisor for a, b, c

and then take any common divisor t and prove that t|d

👌🏿

[sacred junco]

I don't understand the part where it says d=gcd(pq-1, p-1) = gcd(q-1, p-1)

How did it get that?

pq-1-q(p-1) = q-1

from this

Euclidean algorithm

Oh euclidean algorithm

haha

I see now

thank you

[light flicker]

How do we show that x^2 = a (mod p^n) has at most two solutions

2 is not a prime

Okay I think this is only true when a is not divisible by p, but I can't think of a counterexample

[sacred junco]

https://en.wikipedia.org/wiki/Lagrange's_theorem_(number_theory)

[light flicker]

Yeah, so it does say that "If the modulus is not prime, then it is possible for there to be more than deg f(x) solutions."

[sacred junco]

still relevant though

maybe

x^2 = 0 (mod 9)

[light flicker]

oh yeah duh

[sacred junco]

x = 0, 3, 6

[light flicker]

Okay, I proved it for the case when a is not divisible by p, so we done

[sacred junco]

show me

[sterile pumice]

Zopherus:

Zopherus:

Zopherus:

Zopherus:

[sacred junco]

Thank you

[light flicker]

Pretty neat exercise actually

[shy wave]

Really nice @light flicker

Another way to see it maybe is that if p doesn't divide a then we're in (Z_p^n)* which is cyclic (for p>2). In a cyclic group x^2=e has 1 or 2 solutions (respectively if the order is odd or even).
In our case hence x^2=1 has 2 solutions, so the kernel of x->x^2 has two elements and then by cosets of the kernel one sees x^2=a has 0 or 2 solutions

[light flicker]

@shy wave ah that's much cleaner

[shy wave]

@light flicker It uses that (Z_p^n)* is cyclic though
I think I read it is sort of an advanced result

Is there an elementary proof of it, by the way? I've been often curious about it

[sacred junco]

https://math.stackexchange.com/questions/314846/for-what-n-is-u-n-cyclic

[shy wave]

@sacred junco he just shows that if U_n is cyclic then
n=2, 4, p^k, 2p^k (p>2 prime)

He doesn't show the other direction

He actually even uses that U_p^k is cyclic in his proof of the thing above

[sacred junco]

hmm.. you're right

[shy wave]

I searched too something on it some time ago

[sacred junco]

theorem 3.3.1? http://pi.math.cornell.edu/~mathclub/Media/mult-grp-cyclic-az.pdf

[shy wave]

That is the proof for (Z_p)^*

The special case where k=1

[sacred junco]

doesn't seem like there's an easy proof

[shy wave]

As a proof I remeber finding someone invoking the theorem for which a finite subgroup of the multiplicative group of a field is cyclic
Or someone proving that if ξ generates (Z_p)^* than ξ or ξ+p generates (Z_p^k)^*

But yes they weren't at least to me elementary proofs

[light flicker]

The proof I know of is in Ireland Rosen

It's elementary, but not very short

I'd be interested in knowing a short proof, even if it isn't elementary

That might reveal more about why such a thing would be true

[south glacier]

is there a term for 2 sets X and Y if there exists a bijection between them? (i.e. similar to how we say 2 sets are isomorphic if theres an iso between them)

[sacred junco]

you can say they are isomorphic

it works as well as long as we remember what structures we are working with

[south glacier]

well, in particular im trying to (concisely) describe the standard relation between the complex plane and the Riemann sphere

Do we have an iso there with vector addition and complex multiplication?

[sacred junco]

Compactification of the complex plane

how do you define multiplication/addition on the riemann sphere

[south glacier]

maybe introduce a change of variables?

because typical translations arent taking us around a sphere in the same way as around a plane

we would obviously need 1/(z + w) = (1/z)*(1/w) whatever the operation * is (and same with multiplication)

so (re^ia + se^ib)^-1 = re^-ia * se^-ib

ok I just looked it up

the stereographic projection from the sphere onto the plan is bijective, smooth, and conformal, but obviously not isometric.

So if the projection isnt isomorphic then maybe we can find some other mapping for this

[woven phoenix]

Hello everyone. I'm having a trouble proving this statement:

if a, a not equal 1, has order t (mod p), show that a^(t-1) + a^(t-2) + ... + 1 = 0 (mod p)

I have proven it when t = p - 1, but not for other cases

[light flicker]

What did you do in the case where t = p - 1?

[woven phoenix]

well, in that case a^(t-1), a^(t-2), ..., 1 are just a permutation of 1, 2, 3, ..., p - 1 and there are EVEN numbers of them

so the sum is [(p - 1) + 1] + [(p - 2) + 2] + ... = 0 (mod p)

but we cannot always find such neat pairing for other t

for example, when p = 11, consider the case a=3 which has order 5

[light flicker]

Right, but there's a nicer way

[woven phoenix]

the sum is 3 + 9 + 5 + 4 + 1 which does not pair nicely

wow really, what nicer way?

[light flicker]

If a has order t

Then you know that a^t = 1 (mod p) which you can write as a^t - 1 = 0 (mod p)

Think about this equation

[woven phoenix]

hmmm, let me mull over it

[light flicker]

Yep

Nice job

[woven phoenix]

wow, thanks a lot!!!

were you just itching to factor a^t - 1 when you see it?

I wanna know the intuition behind trying the approach above ><

[light flicker]

I mean kind of

You just recognize the sum a^(t-1) + ... + 1

and know it's related to a^t - 1

[woven phoenix]

I see

[sacred junco]

I am making a new exercise to use Bezout’s identity to find the multiplicative inverse of an integer in Zp.
I want to see if I am right. I choose 7 as p and 3 as random element of Zp.
I finally found 1/3 mod 7 as result. I am going to show you how I did:

gcd(a,p)
xa+yp = 1 (1 is the identity element)
x3+yp = 1 (1 is the identity element)
x3+y7 mod 7 = 1 (1 is the identity element)
x*3+0 = 1 (1 is the identity element)
x = 3^-1
x = 1/2 mod 7

thank you

[light flicker]

what

Okay on the last line you probably meant to write 1/3 mod 7

But no that's not the point at all

[sacred junco]

yes

[light flicker]

1/3 is not an element of Z_p

The elements of Z_p are {0,1,2,3,... p-1}

1/3 is never going to be one of these elements

[sacred junco]

ok so the multiplicative inverse must be in the set?

[light flicker]

Of course

[sacred junco]

ok I see

[light flicker]

That's the definition of a multiplicative inverse

I really think you should follow my advice and read a book on proofs

It seems like you don't really understand how to read definitions and how to work with them

[sacred junco]

my book also include proofs but I try to just use them before. I will stop to ignmore them next and I will see the old prooves that I ignored

[light flicker]

Of course your book includes proofs, it's an upper level math book. The whole point is proofs

[sacred junco]

there is already a chapter on proof of the bezouth identity

[light flicker]

That's not the point

These proofs are difficult, they're hard

The focus is not on how the proofs work themselves, but just the statements and the proofs

Reading these will not help you learn how to prove things if you're lacking basic understanding like this

You need to read a book that completely focuses on the basic of how to prove things

[sacred junco]

ah ok

[light flicker]

You're just trying to rush things, and from what I've seen, it's not working out at all

[sacred junco]

I used to ignore proof. can I see from the same book and show you that latter if my new approach is enough different to work? then we will see

[light flicker]

From what I've seen, it won't and you'll just waste more time struggling to work with basic proofs, but go ahead

[sterile pumice]

Blitzkrieg:

[sacred junco]

@light flicker ok I am ready to learn how to proove something

do you really think I need a full book of hundreds of pages?

[light flicker]

Yes

Read How to Prove It by Velleman

[sacred junco]

@sacred junco the book has a first page but do I need to read all?

[light flicker]

Yes

Read all of it

[sacred junco]

ok

@light flicker ok

[light flicker]

You're basically trying to build a house by starting by building the roof

[sacred junco]

@light flicker at least the 3 first chapters?

[light flicker]

All

of

it

[sacred junco]

the third is about proof

ok

[light flicker]

You need to know this stuff

And if you already know it and are comfortable with it, you'll be able to understand it and do the exercises quickly

[sacred junco]

@light flicker I am reading the book. what exactly is my questions had let you think I have to read the book?

[light flicker]

What?

[sacred junco]

@light flicker what has let you think I have to learn to proove?

[light flicker]

The fact that you can't do anything at all basically

The fact that you can't understand basic definitions like that of distributive property of a ring

[sacred junco]

@light flicker I am reading the book you recommend. I also will continue to read it until the end. but I think I understand the distribution of a ring

😦

[light flicker]

You definitely do not

Here I'll give you the benefit of the doubt

You know how matrices add and multiply right

[sacred junco]

yes I worked with a long time ago I think I may remember.

if you give me 2 matrices I can add and multiply these

🙂

[light flicker]

Okay

Then prove that the set of 2 by 2 matrices with real number entries form a ring

Under the addition and multiplication that you know

[sacred junco]

can you give me the values of the matrices?

ah yes you mean proove

I did not see

I will do it

[light flicker]

If it weren't primitive, it'd contradict the minimality of w

Then it's not a primitive pythagorean triple?

Primitive means that all of x^2, y^2 and w are coprime

Then how can there be a prime that divides x^2, y^2, w once?

If a prime divides x^2 once, then it must divide it an even number of times

So you get a smaller solution for x

Okay let me write this out

We have prime $p$ such that $p \mid x^2$ and $p \mid w$, then we have that $p^2 \mid x^2$

[sterile pumice]

Zopherus:

[light flicker]

This means that $(x/p)^2, (y/p)^2, w/p$ is new pythagorean triple

[sterile pumice]

Zopherus:

[sacred junco]

by definition of the distribution of a ring, if for a,b and c 3 elements of the set of the ring and + and X are the operators of the ring, if the additional operator distribute over the addition operator such as:
a*(b+c) = ab+ac, then the ring distribution is proven.

But in the matrices operations

[a b] X [e f]
[c d] [g h]

we have:
[ae+bg af+bh]
[ce+dg cf+dh]

then the ring is distributive

ok my "demonstration" is shitty

@light flicker I think now I see what you mean

[light flicker]

Yeah no this isn't even close

[sacred junco]

@light flicker you did not tell me to proove it is close. just to proove it was distributive

[light flicker]

I mean

I did

[sacred junco]

"Then prove that the set of 2 by 2 matrices with real number entries form a ring" ah yes

[light flicker]

But that's not what I was trying to say

I was saying that what you did isn't even close to correct

It is very far away from being correct

[sacred junco]

😦

[light flicker]

And this is why I want you to read that book

[sacred junco]

ok I read

[light flicker]

Have fun

[sacred junco]

can I get an overview of what it should look?

thank you

[light flicker]

nah

[sacred junco]

ok

[light flicker]

It won't help you

At all

[sacred junco]

ok

[light flicker]

Until you read that book

[sacred junco]

@light flicker where can I ask about proofs? I am about the book

[light flicker]

#proofs-and-logic

Yeah he's not going to understand that I tried for a whole day yesterday

[sacred junco]

cool

[sacred junco]

@light flicker savage af

“The fact that you can't do anything at all basically”

I didn’t know this Discord server could have so many funny snipplets

[sacred junco]

why is the argument: "Jane and Pete won’t both win the math prize. Pete will win either
the math prize or the chemistry prize. Jane will win the math prize.
Therefore, Pete will win the chemistry prize." valid?

by definition a valid argument exists when each premises can not be true if the conclusion is not true. Here, I think the first premise can be true even if Pete will not find the chemistry prize because Jane and somebody else can do it instead. But I am sure I am wrong because the correction of the exercise show that. thanks

[light flicker]

Use #proofs-and-logic

[sacred junco]

ok

sorry and thank

[frank reef]

I'm reading A Classical Introduction to Modern Number Theory. In the proof of the division algorithm, they say

Proof. Consider the set of all integers of the form a - xb with x \in Z. This set includes positive elements. Let r = a - qb be the least nonnegative element in this set. We claim that 0 <= r < b. If not, r = a - qb >= b and so 0 <= a - (q+1)b < r, which contradicts the minimality of r.
How do they get 0 <= a - (q+1)b < r?

[frank reef]

Let me try to digest that.

[frank reef]

I am not seeing it now. I'll come back to this later.

[light flicker]

@frank reef still confused?

[frank reef]

Yes, I'm still confused. I don't see where the inequality comes from, even though Blitz adequately explains where the a - (q+1)b comes from, I don't understand why it must be less than r.

Ok, I think I got it. r is already the smallest element in the set, so if r-b >= 0, which happens when r>=b it must be smaller than r, which is the contradiction.

[frank reef]

Though, it still leaves me wondering why they write 0 <= a - (q+1)b < r because that seems to only confuse the issue.

[light flicker]

Sorry I misread, I'm not sure why you think that confuses the issue

As Blitz pointed out, you have that a - (q + 1)b = r - b < r

[frank reef]

Yeah, I think I get that, but now I'm wondering why they write it as 0 <= a - (q+1)b < r in the book, because r - b < r seems a lot clearer to me.

[light flicker]

because writing it as a - (q + 1)b makes it clear that it's actually in the set that you care about @frank reef

[frank reef]

Ah.

[sacred junco]

I need some assistance

[frank reef]

Here is an algorithm to calculate integer approximation to a square root.
https://hg.mozilla.org/projects/nss/file/default/lib/freebl/mpi/doc/sqrt.txt
How does the author know "it's done" when t==0? And why is it "one plus the square root"?

[light flicker]

t is the error between what you want and what you have already

So if it's 0 you're done

[frank reef]

Ok. So how does one understand/explain why the algorithm gives "one plus the square root" -- i.e. why is there x=x-1 at the end?

[light flicker]

Most likely cause they're only trying to find the largest integer greater than or equal to sqrt(x)

[frank reef]

Hmm. I gave this algorithm a try, and found it gives 3 = my_sqrt(16) -- which I can easily fix by observing that when t==0 before the division by u we have an exact match for the square root, and can stop.

So I was trying to understand the logic behind the x=x-1 at the end.

[light flicker]

Does it return the right thing for like my_sqrt(17)

[frank reef]

Let me test it.

my_sqrt(17) == 3 so I guess not.

[light flicker]

Yeah the algorithm is probably just wrong

[frank reef]

That's a slight disappointment.

[light flicker]

Think the general idea is right, you may just be able to remove the x = x -1 part

[frank reef]

I'll give it a try on some values and see what happens.

Without the x=x-1 and checks for an exact match I get my_sqrt(25)=6, my_sqrt(16)=4, my_sqrt(64)=9, and my_sqrt(17)=4. So it seems to be off by one sometimes.

There does seem to be a need for x=x-1 some of the time, and some of the time it's not. I'm not certain how to fix that.

[frank reef]

Returning to A Classical Introduction to Modern Number Theory, I have this definition.

[sterile pumice]

myrkraverk:

[frank reef]

What exactly am I looking at here? I would guess we're defining the set of polynomials, though the notation (a,b) for it is alien to me.

Subsequent to this definition, we have

[sterile pumice]

myrkraverk:

[frank reef]

What does (a,b)=(d) mean here?

I used to be, but I've forgotten it and my textbook is in a different country.

So I cannot easily review (the material I'm used to)

Yeah, that's what the proof in the book does.

Yes. I'm just unfamiliar with the notation, so I don't really (or didn't) get what the book is referring to.

[fringe knot]

any hints for part b?

brute force suggests every natural number that's not a power of 2

[broken igloo]

hmm

So, the thing about every natural number that is not a power of 2, is that it has an odd factor >= 3

@fringe knot can you use that fact to solve the problem?

[fringe knot]

not sure, I'd have to show that any number can be obtained with some a and b

[broken igloo]

Well, say we have a number n=pq, where p is an odd factor >= 3

how would you continue here? @fringe knot

[fringe knot]

either a+1 or a+2b has to be that odd factor...

[broken igloo]

yeah, that's the idea, how would you do that?

and note that both terms can't be odd

[fringe knot]

@broken igloo does this allow me to get any number with an odd factor q?

"fixing" q and "freeing" b

[broken igloo]

let's see

idea looks right

but can be written more constructively

[fringe knot]

are there any subtleties I need to be careful of with a staying above 0

I'm just hoping not

[broken igloo]

if you write constructively, the subtleties wouldn't burn you badly

[fringe knot]

what do you mean by constructive?

[broken igloo]

given p, q, construct a, b

like a, b are (possibly piecewise) functions of p and q

[fringe knot]

ok, I should be able to just extend from what I have to get that, right?

[broken igloo]

well, yeah

you have found that it splits into 2 cases

so that would be really important

[fringe knot]

@broken igloo do you think this works as a proof?

[broken igloo]

looks okay

[cinder sigil]

Do you guys know of any number that can be written as the sum of two cubes, in 3 distinct ways? I can only find numbers that either has one two pairs, for example: 1729=1^3+12^3=10^3+9^3 or 152=5^3+3^3

[light flicker]

1438201910159509320

@cinder sigil \

[cinder sigil]

How the hell did you find that? @light flicker

But thanks

[light flicker]

Found it in a book

https://books.google.hu/books?id=BeFIIvcBT80C&pg=PA416&lpg=PA416&dq=sum+of+two+cubes+in+three+different+ways&source=bl&ots=oWOw7tPkRQ&sig=ACfU3U2MyM2LMbOvAQdVC4g8iKGGUaTrUA&hl=en&sa=X&ved=2ahUKEwiIk4mK-cvkAhXKlYsKHZ28AoEQ6AEwF3oECAkQAQ#v=onepage&q=sum of two cubes in three different ways&f=false

It's some elliptic curve machinery

I could try to explain if you want but

[cinder sigil]

It's OK

[sacred junco]

How is it possible a residue to be 2^(-5)

[light flicker]

What?

[sacred junco]

I am reading a solution

obviously
2^11-2^5+1=0 mod 2017
So 2^5*(-63)=1 mod 2017
So - 63= 2^(-5) mod 2017

The problem is

What does the last statement really mean

[light flicker]

First think about what 2^(-1) means

[sacred junco]

this math is far too complex for my 8th grader brain

explain

[balmy night]

i was wondering if someone could critique my proof of an infinite number of primes

[hollow bramble]

thats kinda the usual proof that primes are infinite isnt it? looks alright to me

[north surge]

@sacred junco think of 2^(-5) as simply (2^(-1))^5. So basically, the multiplicative inverse of 2 mod 2017, to the fifth power.

[sacred junco]

S=1-63+63^2-63^3...+63^400

What is S mod 2017

[light flicker]

What have you tried? @sacred junco

[sacred junco]

Well 2^11-2^5+1=0 mod 2017

==>-63*2^5=1 mod 2017
==> - 63=2^(-5) mod 2017

and that's about it

Of course the result I replace in S

But nothing interesting happens

Tried to use the fact that if you have 1+a^2+a^3...a^n=a^(n+1)-1/a-1

But nothing

[light flicker]

Why couldn't you do anything with that last fact?

[sacred junco]

I get
((63^(401)-1)/(62)) - 2*(63+63^3..63^399)

But from there I cannot really reach a conclusion

I feel like there is something there

But I cannot find it

[light flicker]

Are you sure you're using the right value for a

[sacred junco]

Yea pretty sure

[light flicker]

Think about it again

[sacred junco]

Well a is 63 so
When the equation is
1+63+63^2...63^400-2(63+63^3...63^399)

So the first part by the formula is that

[light flicker]

Think about your original equation

What's the common ratio

[wary dune]

wait so

a^(p-1) ≡ 1 (mod p)

can someone explain this

[shy wave]

@wary dune did you see
a^(φ(n)) ≡ 1 (mod n) ?

[wary dune]

no

is that the same thing

i don't understand it

[shy wave]

No just a more general statement

Have you dealt with group theory?

But don't you understand what that is saying?

[wary dune]

im not exactly sure but i think it's something about 1 being the remainder when a ^ (n-1) is divided by n

[stuck lintel]

@wary dune You might already know this but it's called Fermat's little theorem

It's a specific case of euler's theorem for when the modulus is prime

Anyways if you need help understanding why it's true or how to prove it, let me know

[lucid pike]

Hey, how do I prove that gcd(a,ab)=a for integers a and b?

It's so intuitively true I cannot think of any way to prove it

Sorry if this is a dumb question

[light flicker]

The gcd is the biggest number that divides both numbers

[lucid pike]

Yeah I know

What do I do if I am asked to provide a rigorous proof?

[light flicker]

a divides both numbers

so the gcd must be a multiple of a

[lucid pike]

Yup

Ah

Im dumb

[light flicker]

but thats just it

[lucid pike]

Thx

[light flicker]

a is as big as you can divide a by

[lucid pike]

Thanks, it was obvious after all

[stuck lintel]

also since we know gcd(ka, kb) = k*gcd(a,b), you can just say gcd(a,ab) = a*gcd(1,b) = a since 1 is coprime with every integer

[wind falcon]

Hey! Stuck trying to prove a lemma. Anyone mind helping?

I want to show for a, b in N, gcd(a,b) = gcd(a%b, b)

[light flicker]

What is %?

[wind falcon]

Modulus

[light flicker]

And what's your definition of gcd?

[wind falcon]

So like the remainder for integer division

Euclidean def

[light flicker]

I'm not sure what the Euclidean definition is

[wind falcon]

Ok

Uh

Are you fine with reading code?

[light flicker]

Sure

[wind falcon]

   requires a > 0 && b > 0
{   
   if a == b then a else
   if b > a then gcd(a,b - a) else
    gcd(a - b,b) 
}```

[light flicker]

Well

Okay in this case, you should just think about gcd(a,b)

And run it through your code and see how it reduces down to gcd(a % b , b)

[wind falcon]

Yeah :/

[light flicker]

Still confused?

[wind falcon]

If it were pen and paper proofs

It would be easy

[light flicker]

This is essentially pen and paper

[wind falcon]

It's just that the proof verifier is very nitpicky

I'm essentially trying to figure out the most basic proofs with minimal theorems to use

[light flicker]

You don't really need to use any theorems here

Just split it up into two cases

What happens when a < b?

[wind falcon]

No, like I have to define things like a|b. And it can't see the equivalence of a|b and there exists a c s.t. b = a*c.

[light flicker]

you don't need to use a | b here at all

[wind falcon]

Ok

I'll try

I found something I did a while ago and it seems to work with it

[light flicker]

Just think about two cases

when a < b what happens

[wind falcon]

yeah

I had a lemma for it

Just needed to use the fact that a%b = a - (a/b)*b

where / is integer division

[light flicker]

That works

[wary dune]

what does a%b mean

is it the just the integer quotient of a/b without the remainder

[hollow bramble]

a%b is modulo

a mod b

[supple furnace]

If d|b, then d|a-kb iff d|a @wind falcon

[wind falcon]

Thing is the proof verifier doesn't understand the relation between divides, modulus or gcd at all.

I also already solved it

[supple furnace]

This is categorically the shortest proof though

[distant abyss]

i thought you guys would like this

[inner crest]

#chill

$n$ people and $m$ urinals with $n>\left\lceil\frac m2\right\rceil$ means bad.

[sterile pumice]

EpicGuy4227:

[hollow bramble]

If there are infinite pigeons and finite pigeonholes there must be a pigeonhole with infinite pigeons

[fervent crest]

Is it true that the divisor sum function is multiplicative, that $\sigma_x(nm)=\sigma_x(n)\sigma_x(m)$ if $\gcd(n,m)=1$

[sterile pumice]

Whoever:

[fervent crest]

It is ok

[light flicker]

yes this is true

[slender coral]

So im stuck on this problem where they want me to write the product of the primenumber factor 45, (apologize if the problem sounds weird im trying to translate it), i get it to 5*9 but the back of the math book where all the answers are says its 3 * 3 * 5, am i thinking of it in a wrong way (also sorry for bothering with very basic problems im just rusty as hell and math was never my strong subject, just trying to get into it by myself

[plain fable]

no, you're right

you are in the middle of it

you just haven't reached the final step

[slender coral]

hmm

[plain fable]

45 = 5*9

is 5 a prime number?

[slender coral]

.. idk

im so dumbbb

[plain fable]

do you know what a prime number is?

[slender coral]

a number only divideable by 1 and itself?

[plain fable]

yes

[slender coral]

ok so

[plain fable]

so is 5 a prime number

[slender coral]

5 is prime

[plain fable]

yes, correct

is 9 a prime number?

[slender coral]

ok so whats the next step

hmm no

[plain fable]

ok, then you split it up

what can you split 9 into

[slender coral]

3x3'

[plain fable]

yes

[slender coral]

i guess

[plain fable]

so 45 = 5*9 = 5*3*3

is 3 a prime number

[slender coral]

yes

[plain fable]

ok, so now everything is a prime number

[slender coral]

ok so i get the numbers as low as possible

[plain fable]

and you're done

that is prime factorization

[slender coral]

alright thanks i super appriciate u helping me out

[plain fable]

np

[slender coral]

another question

This tree thing

once i hit a prime number, do i just stop with the side entirely?

[plain fable]

yes

[slender coral]

ok

[plain fable]

you can't branch a prime number

it's just itself and 1

[slender coral]

oke

[plain fable]

and you don't write 1

so it ends there

[slender coral]

thanks alot again

[slender coral]

so

can negative numbers be prime

i googled it and it says no, yes and it doesnt matter as the 3 answers to that question

[plain fable]

probably would just keep using positive prime numbers

and add a new unit of (-1) that multiplies the numbers

if we have negative primes, then the unique factoring theorem would break down

[slender coral]

problem tells me to explain why -31 is not a prime number

i just wrote cuz its lower value than 1

i asume i just ignore negative prime numbers for now

[light flicker]

It really depends how you define a prime number

[plain fable]

extending primes past positive integers does get weird

there are sensible ways to do it though

like Gaussian Primes in the complex domains

[slender coral]

is there a way to check if somethings a prime number quickly

for example 879, 359 etc

big numbers

[plain fable]

try dividing it by every prime number less than the square root of itself

if you find no prime numbers smaller than the square root of the number that divide the number

[slender coral]

i dont even know how to use square root fml

[plain fable]

the number is a prime

[slender coral]

nvm solved it, thanks

[slender coral]

im stuck

"give example of three prime numbers whose amount/value is 61"

idk what to do here

[mighty dew]

prime decomposition?

is it asking which three primes multiply to 61?

[craggy solstice]

so their sum is 61?

is it asking which three primes multiply to 61?

[slender coral]

sec ill google translate

im bad at translating myself

[craggy solstice]

thats just stupid

lol ok

[mighty dew]

61 is prime 🤤

[slender coral]

give an example of three prime numbers whose sum is 61.

this is what the question says

[woven phoenix]

weak goldbach conjecture: Every odd number greater than 5 can be expressed as the sum of three primes (might be same primes)

[mighty dew]

oh

[slender coral]

all the info i get

also can u explain aswell pls

[light flicker]

just play around with it

[woven phoenix]

so just find the numbers by trial and error

[light flicker]

What have you tried?

[slender coral]

idk what to even try

[woven phoenix]

3 + 5 + 7 = ???

3 + 5 + 13 = ???

try many combinations

[craggy solstice]

take nearer prine numbers to 61

[mighty dew]

is there even an algorithm to do this? seems like a weird guess and check question

[craggy solstice]

try to lessen difference and express inform of trivial primes

[woven phoenix]

@mighty dew it's just to test your understanding of primes

[craggy solstice]

so no algorithm?

[slender coral]

wait i do plus?

[woven phoenix]

sum means "plus"

[craggy solstice]

uhm what?

[slender coral]

uh

doesnt sum mean the end value

[craggy solstice]

...

[slender coral]

im confused

[woven phoenix]

@craggy solstice if there is an algorithm, it means you've solved the goldbach conjecture (an unsolved problem in math)

[light flicker]

sum does mean the end value yes

sum means the end value when you add two things

[slender coral]

ya

[light flicker]

@woven phoenix that statement makes no sense

[slender coral]

ok so i just plus up lots of different prime numbers til i get 61?

[light flicker]

They tell you how many to add together

[slender coral]

umm

ok so

3 prime numbers together is 61

i dont even understand the question honestly

[woven phoenix]

@light flicker so, what algorithm should I use to find 3 primes that add up to 2^43112609 - 1 ?

[light flicker]

@woven phoenix that doesn't mean an algorithm would solve the goldbach conjecture

And there are algorithmss

Here, I'll try to sum up all triples of primes less than your number

[woven phoenix]

If you can find an algorithm that provably works for all integers n, it means you solved it right?

[light flicker]

There that's your algorithm

That makes no sense

the weak goldbach conjecture and the goldbach conjecture are different problems

[woven phoenix]

"I'll try to sum up": which means that the algorithm might or might not succeed

[light flicker]

I know they exist

The weak goldbach conjecture has been proven

[woven phoenix]

ah sorry, I conflated the weak goldbach conjecture and the goldbach conjecture then...

[light flicker]

"the weak goldbach conjecture and the goldbach conjecture are different problems"

[woven phoenix]

yeah

[light flicker]

Even regardless, this is still a perfectly fine algorithm

If you try all triples and find that they don't sum up to it, then you've found a counterexample to the conjecture

Otherwise you'll find one

[woven phoenix]

@slender coral can you tell me what is the answer to: 5 + 3 + 7 = ???

(5, 3, and 7 are all primes)

[slender coral]

15?

[woven phoenix]

right... so it's not 61

[slender coral]

ye i found a solution

[woven phoenix]

the problem asks you for 3 primes that add up to 61

[slender coral]

37+7+17

thought they wanted something entirely different

[woven phoenix]

cool, you got an answer 🙂

[slender coral]

thanksthanks

[thorny sparrow]

So, one of my friends sent me this problem, and after hours of trying to figure it out I came up with this

I'm just curious if there is anything wrong with the way I did it?

[broken igloo]

I'm guessing vieta jumping is the idea here

[thorny sparrow]

Yup

[craggy solstice]

is this a joke or what lol

[thorny sparrow]

It's not a joke. Just looking for some guidance on how to fix my proof

[craggy solstice]

do you know where the problems from and its significance

stop kidding

whatever, your solutions interesting

[inner crest]

wasn't this the problem that made everyone learn vieta jumping?

[quick furnace]

yes

[thorny sparrow]

Tbh, at first I didn't know. A few hours into it I looked up the problem and found out about the history. I got the hint about vieta jumping and thought I'd give it a shot without looking at the proof.

[slender coral]

is there a way to quickly find a solution to big equations like 7*27 etc

without calc

[light flicker]

What do you mean find a solution to

[slender coral]

like sum

[light flicker]

That's just a number, there's no equation to solve

• is usually used to mean product

[slender coral]

oh

well

nvm idk how to phrase it

[light flicker]

Well think about it and then try again

If you don't know how to describe it then you don't really understand your own question

[slender coral]

i do im just garbage at english sometimes

[light flicker]

Well that's why math language is a thing

[slender coral]

ok so

7*27= 189

189 is the sum right?

[light flicker]

No, 189 is the product

[slender coral]

oh ok

[light flicker]

Sum is for when you add two numbers together

[slender coral]

ok so my question is

how can i find the product of big numbers without doing head math thing

is there a trick to find the product quicker

[light flicker]

Not really

[slender coral]

ah

alright, thanks anyway ^^

[craggy solstice]

well breaking down in smaller forms might

11*12= 12x(10+1)

you dont even have to think for these

[light flicker]

Why did you use both * and x to mean multiplication in the same line

[stuck lintel]

grats on yellow zoph

[light flicker]

thanks how amc studying going

[craggy solstice]

@light flicker to avoid italics lol

[stuck lintel]

it's going good

still trying to keep the usamo dream alive :^)

[light flicker]

Tell me when you make the imo team so I have 1/6 chance of doxxing you

[craggy solstice]

😂

[stuck lintel]

lmao

[jade sentinel]

@craggy solstice Use \* text \* to avoid italics

* text *

[slender coral]

anyone mind helping me out

problem: which fraction should be added to 3/8 for the sum to be 13/16

[light flicker]

You should start using #prealg-and-algebra, this channel isn't really suited for this type of discussion

[slender coral]

ok

[craggy solstice]

lol

well this might be very basic number theory

[sturdy dirge]

Not elementary number theory.

[peak turtle]

how do i find all solutions of the linear congruence 3x-7y congruent with 11 (mod 13)?

[light flicker]

Solve 3x - 7y = 0 (mod 13)

Then find a single solution to 3x - 7y = 11 (mod 13)

[peak turtle]

@light flicker how do i solve for 3x-7y

[light flicker]

What

[broken igloo]

Actually, just go through all x mod 13, then for each x solve for y

[light flicker]

What would you do for a much larger modulus then

[peak turtle]

how do i solve for 3x-7 congruent with 0 mod 13

like, what do i do with the y

[broken igloo]

well, but you wanted all solutions...

y mod 13 is linear in x mod 13, so I guess we can just solve for x mod 13 as 0 and 1

[sacred junco]

@light flicker okay mane. I need to prove the gcd(a,b)=gcd(r,b). the r is from the Euclidean algo with a=cb+r. I have started, but i dont think i am getting anywhere

[light flicker]

Try showing that gcd(a,b) = gcd(a-b,b)

[sacred junco]

i did, but i just realized i think i prove wrong

so i need to fix

[light flicker]

That completes it right? What else do you need to do?

[sacred junco]

hmm... i think it may, but there is a greater than or equal too and greater than difference that maybe issue. idk

[toxic breach]

It depends on what definition you use. If you use the natural one (not the one with Ideals), you just have to take literally one common divisor named d and then, d divides a and b. so d divides a-cb=r then d divides b and r.
This shows that the set of common divisors of a and b is included to the one with b and r.
So if we take a common divisor of b and r, we have a=cb+r so it divides a.
Then both sets are equal. So they have the same smallest element. So gcd(a,b)=gcd(r,b).

[amber basin]

I need to go about proving that $n | (n+1)^n - 1$ where n is a positive integer.
Kinda stuck on how to go about doing this.

[sterile pumice]

wazabear_notabear:

[torn escarp]

I know it can be shown with the lifting the exponent lemma, but maybe there's another way

[amber basin]

I'll look into that, but I don't believe it was intended for me to solve it that way 🤔

[torn escarp]

actually looks like a stronger condition might hold and actually n^2 divides (n+1)^n - 1

I'm sorta distracted at the moment but I might be free in a bit to try to think about some other kind of method, what sort of techniques have you been learning in class?

[amber basin]

right now just the basics, only first week of class. things like direct, induction, contradiction, etc...
nuttin fancy, is why i'm slightly confused

[torn escarp]

oh maybe try induction then

[amber basin]

that was my first thought

[torn escarp]

1 clearly divides (1+1)^1 -1

then try to use that to boot strap haha

yeah that's tenuous at best but if it's meant to be solved with those tools it's worth a shot

[amber basin]

i felt like it was getting me nowhere, but i'll give it another shot

[torn escarp]

$(n-1) | n^{n-1}-1$

[sterile pumice]

Merosity:

[torn escarp]

assume this

it really looks like it is related to a geometric series if that's the case

$\frac{n^{n-1}-1}{n-1} = 1+n+n^2+\cdots + n^{n-2}$

[sterile pumice]

Merosity:

[torn escarp]

if you're familiar with this

[amber basin]

yeah, thanks
i'm going back in!

[torn escarp]

good luck, I'm off I'll check back in maybe 30 min or so, no promises lol

[amber basin]

no luck tonight, i've been working on this problem for literally hours
hopefully a fresh pair of eyes tomorrow will make me see something

[wild zinc]

you want to use ||binomial expansion||

[toxic breach]

I think it’s pretty painful to use induction for this problem. Why not just use ... yea, this xD

[wild zinc]

alternatively ||modular arithmetic|| makes it trivial

[toxic breach]

Yea too

But the other method gives the n^2

[wild zinc]

but the ||binomial expansion|| method makes the conjecture that n^2 divides it more obvious

yeah :^)

[toxic breach]

Lol stop reading in my mind x)

[wild zinc]

haha sorry :^)

looks like the geometric series also just solves instantly?

(n+1)^n - 1 = (n+1 - 1)((n+1)^(n-1) + ... + 1) = n((n+1)^(n-1) + ... + 1) and hence is divisible by n

[torn escarp]

oh nice

[amber basin]

thanks everyone, you’re all life savers

[waxen wave]

I want to make sure I have the right concept. If the GCD does divide the number I am given then I will have to find x? If the GCD is 1 it will always have an x. What happens if it’s 1(mod 20)

Is it okay he inverse?

,rotate

[dim ocean]

i dont understand what ur are saying, but one solution for the above problem is x=3

[fickle schooner]

you are looking for 20|7x-1

[waxen wave]

Does x=3 from doing bezout identity

After doing that?

After getting x and y from bezout identity

7x+20y=1

I would have to find x and y from doing bezout identity and then I’ll get x=3 which will be the answer @dim ocean said

[waxen wave]

Anyone? 🧐

<@&286206848099549185> 🧐🧐

[light flicker]

What exactly is your question

[waxen wave]

I want to make sure I have the right concept. If the GCD does divide the number I am given then I will have to find x? If the GCD is 1 it will always have an x. What happens if it’s 1(mod 20)

Is it okay the inverse?

[light flicker]

This still makes no sense at all, I have no clue what you're trying to ask

[waxen wave]

How come my mentor does know what I’m saying 🤔

[light flicker]

Because he has the context of what problems you're working on?

And what you're studying in general?

None of which I have

[waxen wave]

But the problem is literally in the picture I sent

[light flicker]

I didn't see this picture at all

Your question still really makes no sense, which "given number" are you talking about

[waxen wave]

After the equivalence sign

Like 1,5,8 or 2

[light flicker]

Also, the GCD of what

[waxen wave]

I just got what @fickle schooner which was x=3

Thanks @fickle schooner

[waxen wave]

Okay this one I’m pretty sure is no solution

,rotate

[waxen wave]

It’s no solution

Thanks for the help. Guess what I’m doing is not popular in number theory 🧐🧐🧐

@light flicker

[upbeat wren]

the final answer is right but I didn't check the work.

um x = 1, y = 0 doesn't make 1 on the right.

so I think you need just a bit more explanation 🙂

[light flicker]

This is a popular type of question

It's just not super clear what your work js

[weary sigil]

Is there something like the extended Euclidean algorithm for more than two numbers?

Like, to find a, b and c such that ax + by + cz = gcd(x, y, z)

[light flicker]

Just apply the euclidean algorithm to the first two to find a,b such that ax + by = gcd(x,y), then find d,c so that d*gcd(x,y) + cz = gcd(x,y,z)

Since gcd(x,y,z) = gcd(gcd(x,y),z)

[weary sigil]

oh, and then a' = da, b' = db?

[light flicker]

yeah

[weary sigil]

hmm, I was hoping to use the bounds the algorithm provides on the coefficients in a proof

[light flicker]

Well you might still be able to

[weary sigil]

hmm, a' = da <= d * x/d = x

yeah, that works

wait, no...

anyway, thanks!

[waxen wave]

@upbeat wren I erased it and since 1/7 does not divide 1 it has no solution. That was an old picture

For this problem do I assume And consider a set of 5. {0,1,2,3,4}?

[lucid pike]

How do I prove that there are infinitely many composite pairs of the form (6n-1,6n+1)

[stuck lintel]

Euclidean algorithm

Also @waxen wave it’s true for any b coprime to 5

[waxen wave]

@stuck lintel thanks

[lucid pike]

Euclidean algorithm as in the GCD algorithm?

How would that help

@stuck lintel

[stuck lintel]

I’m assuming composite pairs means not relatively prime right?

[light flicker]

Nah, he means that both are composite I think

[stuck lintel]

Oh..

[light flicker]

Although not relatively prime implies that both are composite

[lucid pike]

yes, zoop is right

[stuck lintel]

:(

[light flicker]

It's not too hard to just find an infinite sequence of such n I think

[lucid pike]

Apparently if n=20+77k for k in Z^+, all numbers of the form 6n-1 and 6n+1 are composite

[light flicker]

Yeah

[lucid pike]

It is true, but I don't see the line of reasoning that would lead me here

[light flicker]

Well 77 = 7 * 11

And the idea is that you want 6n -1 to be divisible by 7

and 6n + 1 to be divisible by 11

Or vice-versa it doesn't really matter

[lucid pike]

Ah damn I see it now

Thanks

[light flicker]

You can do the same thing with any two primes

any two primes bigger than 3 at least

This is kinda the idea of chinese remainder theorem too

[lucid pike]

That makes sense, thanks a lot

[sterile pumice]

euler/fermat:

[light flicker]

What does the prime factorization of squares look like?

More specifically, what is special about the exponents for the prime factorizations of squares

Not sure what you mean by an odd number total

That's true, but not really what I was asking

Think about the exponents

Maybe it'll help if you think about why its true that the number of factors of a square is odd

Given the prime factorization of a number, how do you find the number of factors

I have no clue what you're trying to say

yes

[sterile pumice]

euler/fermat:

euler/fermat:

euler/fermat:

[light flicker]

That's all true yes

[sterile pumice]

euler/fermat:

[light flicker]

Are you sure this is a prime factorization?

[sterile pumice]

euler/fermat:

euler/fermat:

[light flicker]

We want the exponents to be even or odd?

Correct

Yeah

Okay someone help me now

Show that $\binom{x}{(x-1)/2} \leq 2^{x-1}$

[sterile pumice]

Zopherus:

[light flicker]

for x and odd integer

[sterile shadow]

from definition

[winter bear]

hmm

[light flicker]

help pls

@ helpers

[winter bear]

is this a meme lmao

[sterile shadow]

wtf you're not trolling?

ok good one dude

[light flicker]

No I'm serious I actually am stuck on this lmao

[winter bear]

oh

lemme try it then

prolly wont get anywhere if you didnt tho lol

[light flicker]

good luck

I'll give you a lecture on something if you solve it

[sterile shadow]

would you give a lecture on how to solve this question?

[light flicker]

anything you want

[stuck lintel]

Lecture on how to prove Riemann hypothesis

[light flicker]

sure

[winter bear]

hmm doesnt actually seem too hard

start with odd and even base case

and induct with steps off 2

[light flicker]

I only care about the odd case

[winter bear]

well there you go, it actually works out nicely

cause you get an extra factor for each step which is easy to show ≤2

[light flicker]

@winter bear okay you're a genius

what do you want to learn about

[winter bear]

lol teach me some, idk fun combo stuff

[light flicker]

oof okay

@winter bear do you know anything about derangements

[winter bear]

not really

what are they

[light flicker]

Alright let's talk about this

So n men go into a movie theater and each of them gives their jacket to the coat hang person

When they're leaving, they all go back to get their coats

But the person at the coat hang forgot who's coat is who's and just gives them back to the men randomly

One question you can ask is, what's the probability that none of the men get back their own coats

[winter bear]

hmm interesting

first glance, is it like (n-1)/(2n) or smth

[light flicker]

No, it's actually not a very nice expression

[winter bear]

oh

[light flicker]

The nicest way to do it is through inclusion-exclusion

one way to reformulate this question though

Is to think of the coat check person giving back the coats to the men

As a permutation on n numbers

[winter bear]

right

[light flicker]

So the question becomes, how many permutations are there on n numbers that don't fix any of the n numbers

Using, inclusion-exclusion you can come up with the formula which is

[winter bear]

i see, and i am assuming its easier to answer the part which is fix some of the numbers

[light flicker]

$d_n = \sum_{k=0}^n (-1)^k \binom{n}{k}(n-k)!$

[sterile pumice]

Zopherus:

[winter bear]

oh damn

so ways n numbers are in place - number n-1 in place+...

i assume

[light flicker]

Yeah exactly

Now, another interesting question is that

As n -> infinity, what's the probability that no one gets their hat back

[winter bear]

hmm

all this is over n! ofc. so thats just like, e^(-1) right

[light flicker]

That was fast

Yeah it tends to e^(-1)

[winter bear]

i noticed the (n-k)! cancels out lol

its just sum of (-1)^k /k! then

[light flicker]

Yeah exactly

[winter bear]

1/e chance no one gets what they want back, interesting

makes sense i guess, as theres more n, theres more room for the hat to go to someone else i guess

[light flicker]

Yeah

That's basically all I know about derangements

[storm roost]

hey guys im not so sure about the answer of this.

the infimum of this is 0 right?

[swift shard]

Of the sequence 1/n? Yes

[storm roost]

but idk how to present it

inf[0,1/n) = 0?

and sup[0,1/n) = 0 am I correct?

so x must be 0

[swift shard]

sup is 1 here

[storm roost]

why

i thought as n gets bigger the value is smaller

[swift shard]

I'm talking about the set 1/n for all natural n

The largest member of this set is 1

[storm roost]

oh

so x has to be smaller than 1

[swift shard]

But yes the inf is 0

However, that's what you want to prove. I'm not too sure what methods you might have at your disposal?

[storm roost]

idk i just had my first lecture last week and idk what im doing

[swift shard]

Unless you're allowed to declare the inf is 0

Then it's rather straightforward

[storm roost]

so youre saying if the inf is 0, x = 0? i dont quite get that

[swift shard]

x is a lower bound. The question implies that

[storm roost]

actually still dont get the definition of supremum. I thought least upper bound the least value youll get in the upper bound

[swift shard]

Remember that inf and sup apply to sets. What's the set you're discussing?

The set I'm talking about is
{1/1, 1/2, 1/3...}

[storm roost]

my uni didnt even explain what 'sets' are

im sorry if im making you feel like im an idiot

[swift shard]

Nah not at all. You're learning

A set is a collection of anything. In this case, a collection of real numbers

One that's important for this question:
{1/1, 1/2, 1/3...}

[storm roost]

ok. does least upper bound mean the first position within the set?

[swift shard]

An upper bound to the set is any number larger than any member of the set

So 2 is an upper bound, since 2 is larger than anything in the set

The least upper bound is the smallest number that's still an upper bound

[storm roost]

so upper bound in this case is anything greater than 1

[swift shard]

Sorry, I should have said greater than or equal to

Yes, that's exactly it.

So the least upper bound here is 1, since 1 is the smallest number that's still an upper bound

[storm roost]

OK. so i get that. and the inf here would be 0 i guess?

[swift shard]

Yup. The largest number that's still a lower bound is 0

Now, your question implies that x is a lower bound, but 0 ≥ x. Because there's no number larger than 0 that's still a lower bound, x = 0

Oops, I mean x ≥ 0

[storm roost]

right

thank you

[swift shard]

I don't know if you need to prove that inf = 0 though

You could always suggest that any positive number ε is greater than some element in the set.

That is, for some n
ε > 1/n
nε > 1
By the archemedian property that must be true

Wow that was easier than I thought lol

[storm roost]

I think im asked to state it only

[swift shard]

Np. Then we finished earlier

[storm roost]

but im still a little bit unsure about how to construct my sentenced answers since I just had to write down numbers when I was high school

the expression ,inf[0,1/n)=0 is that correct?

[swift shard]

Yus, you could say that

[storm roost]

and sup[0,1/n) would be 1?

[swift shard]

A = {x| x = 1/n, n ∈ N}
inf A = 0
Is the way

And yes the supremium would be 1

Not useful for this question though

[storm roost]

your A represents a set , right?

anything that is denoted by {}

[swift shard]

Yup. I named the set in question A, then said A's infimum is 0

[storm roost]

what does the | mean

[swift shard]

A = {x| x = 1/n, n ∈ N}

A is the set of all x, such that x = 1/n for any n in the naturals

| means "such that"

[storm roost]

does inf[0,1/n) mean the same

[swift shard]

I guess if you're clear than n can be anything

Yeah, that's probably good enough. Ask the teach what they want

[storm roost]

ive got another question

does 0 ≤ a ∈ R mean that a could be natural numbers

[swift shard]

Yes, since natural numbers are also real numbers

[storm roost]

thanks

[fervent crest]

@light flicker I solved the problem easily

Was that a meme?

I feel like it was

I literally proved it using induction

But instead of x+1 I did x+2 each time

[light flicker]

It wasn't a meme lmao

I was stuck for a little bit

I tried using Stirling's approximation for a bit

[craggy solstice]

is there anyway of finding solutions of n degree diophantine eqns

[torn escarp]

a sort of meh method is solve it mod p, then you are guaranteed a hensel lift mod p^k and patch together all the p^k with chinese remainder theorem but this is not usually ideal

[light flicker]

Finding solutions to diophantine equations is equivalent to the halting problem iirc

And of course I mean general diophantine equations

[stiff rivet]

that's hilbert's tenth

so yeah

[light flicker]

Oh woah that's cool

Didn't know that was one of Hilbert's

[stiff rivet]

well not quite

equivalent was solved a lot later

you have to reduce it to the halting problem and vice versa

[light flicker]

Right

[stiff rivet]

needs more reaction emojis

[light flicker]

im not in the us so that flag is wrong

[fervent crest]

whenever zopherus says something smart ill do this

[light flicker]

Do what

Also you'll never get a chance to do it

[wary dune]

hi

can someone help me

prove that 11 | 100q + r if 11 | q + r

[broken igloo]

If 11 divides q+r, then 11k=q+r

continue

@wary dune

[wary dune]

ok

11|q and 11|r ?

wait no

[craggy solstice]

11|99q+(q+r)

99q is always divisble by 11

q+r has to be divisible bu 11

that seems shorter than 11k method

[wary dune]

ok so 11 | q + r and 11 | 99q and if you add them you get 11 | 100q + r

ok thanks

[woven phoenix]

Hi everyone, I need help proving this statement

This is as far as I got

only the a^(p+q-1) is different (the problem requires it to be a^pq) but I can't seem to reconcile it further

Btw I tested numerically, and for all combination of the first 50 primes assigned to p and q (with p != q, and 0 <= a <= 250) the statement is true, so it seems legit

[light flicker]

All integer a?

@woven phoenix

[light flicker]

Okay I figured it out

[woven phoenix]

yes all integer a

wow that's fast ><. could you please give me any hint?

[light flicker]

Well first, just prove that it's divisible by p first

Use the fact that x^p = x (mod p)

And also use the fact that (x + y)^p = x^p + y^p (mod p)

[woven phoenix]

hmm let me try...

[fervent crest]

Can we use euler totient 👀

And the fact that in mod p you can divide

[light flicker]

by euler totient you mean fermat's last theorem

I mean fermat's little theorem lmao

[fervent crest]

Yeah

[torn escarp]

yeah use that

look at it in mod p, everything will cancel fine

[light flicker]

Think you need a little more though

[torn escarp]

$a^{pq}-a^p-a^q+a \mod p$

[sterile pumice]

Merosity:

[torn escarp]

a^p = a so those cancel

(a^q)^p and a^q also cancel same way

so it's 0 mod p

replace p with q and you have the other case and all wrapped up

[light flicker]

Yeah I'm dumb

I used the fact that (a^q - a)^p = a^(pq) - a^p mod (p)

[torn escarp]

more than one way to skin a cat

[light flicker]

don't make that analogy here

[fervent crest]

Bold of you to make that statement in a christian cat server smh

[torn escarp]

haha I need to watch my edge

[light flicker]

Alright, let me give an actually interesting exercise then

If a is relatively prime to some prime p, then show that x^2 = a (mod p^n) has at most two solutions for all positive integers n.

[swift shard]

More than one cat to skin around here