elementary-number-theory

[red yacht]

yes, algebra 1, but is only introduction to algebra really

today in class we touched on chinese remainder, and they already lost me

well, algebra 1 where I study its not exactly abs algebra, we only get introduced to groups and rings, and primitive roots and roots of unity, but those topics are covered in more depth in algebra 2, at least where I study

i see, I didnt know this is my first semester in university

[stuck spear]

is there any analytical way to solve/analyze equations/expressions in integer domain or is it almost always depend on the expression under question, got used to solving equations in real number domain, so these problems in these domain seem very tedious to deal with. for eg., finding the multiplicity of the combinations resulting in the 14th state here, i.e., the last value in the result sequence. may seen easy that it's only (3,3,3) and (5,1,1) but how can check if my result is exhaustive, i.e., if i choose an arbitrary sum and check for the triplets solving it, how can i be sure that my solution set of triplets is exhaustive?

this is the problem under question

[west glade]

see hilbert tenths problem

the answer is no

[stuck spear]

thanks man

[zealous thorn]

How can I solve it?

[loud maple]

This boils down to finding an efficient way to find the highest power of a prime that divides the factorial of a number.

You need to count powers of 2 that occur in 26! while also taking into account numbers between 1 and 26 that are divisible by a greater power of 2 than 2 itself

[zealous thorn]

Ohh it is 7

Thanks

[zealous thorn]

I didn't understand the second part

2^23

[loud maple]

There's a nice standard technique to compute the highest power of a prime that occurs in a factorial.

[kindred fulcrum]

you have 2,4,6,8,10,... that are all even and part of the product defining 26!

but 4 is divisiable by 2^2 and not by 2 just once

so you have to account for that

[loud maple]

Yes, 4,8,12,... have 2² as a factor.
8,16,24 have 2³ as a factor, and so on

[zealous thorn]

Yes

26/2+26/4+26/8+26/16

13+6+3+1

23

2^23 will have( 8)^7(4) so max by my side is 7

[zealous thorn]

My question is about the multiplication n

n.8^k

what is n here?

Is this (4)?

[kindred fulcrum]

no

[zealous thorn]

Does it matter?

[kindred fulcrum]

n will include everything else that is not a power of 8 from 26!

[zealous thorn]

Should i find?

Ahha

[kindred fulcrum]

no, the question doesn't ask about n

[zealous thorn]

Got it!!

Thanks

[pulsar patio]

1^n + 2^n + 3^n +...+ n^n = ?^n

[junior swallow]

Can somebody help me see why this is true

Can it be proved with induction on l?

https://math.stackexchange.com/questions/5030359/questions-on-the-proof-of-theorem-2-in-ireland-rosen-cimnt-if-p-is-an-odd-pri

Looks like others have my question

Is it a mistake?

[tulip vortex]

Isnt this just fermats little theorem

[rugged locust]

doesn't quite work, fermats little theorem tells you that U(Z/nZ) has exponent phi(n)

but doesn't necessarily give the existence of any element of order phi(n), which is what we want

[weary fog]

wheres your beginning renato

[wanton gorge]

Is there any relation between Collatz conjecture and Computer Science?

[unique cypress]

[kindred fulcrum]

You need to be more specific

[wanton gorge]

I mean, if it is useful for Computer Science

Or if there are people using it in any branch of Computer Science

I don't know if I'm being clear 😅

[kindred fulcrum]

Opening up wikipedia there is a section relating a collatz-like problem and the busy beaver numbers.

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

[wanton gorge]

I see, thanks

[tulip vortex]

No I meant the specific step highlighted

[wooden glen]

No.

It's not really useful for anything other than being "a surprisingly intractable question that is very simple to state".

(Which is also the motivation for it showing up in busy-beaver circles -- "very simple to state" turns out to map to "requires only a few Turing machine states to implement").

[nocturne vortex]

Do I have to use the Euclidean Algorithm to solve this? Since (3,9)=3 and 6=3*2, there are two solutions. But since 3|9, I can't find an inverse to solve for x directly.

[west glade]

well 9 is small

you could just bruteforce

so you dont have to use EA

in general you divide an equation like ax+by=c by gcd(a,b) if thats not 1

and then solve the new equation

which now has gcd(...)=1

[nocturne vortex]

ty

[junior swallow]

Is the following true: If ${a_i}{i = 1}^m$ is a reduced system modulo $n$, then $U(\mathbb{Z}/n \mathbb{Z}) \cong \bigoplus{i = 1}^m U(\mathbb{Z}/ a_i \mathbb{Z})$?

[sterile pumice]

okeyokay

[kindred fulcrum]

Wdym by a reduced system?

[junior swallow]

(a_i, n) = 1 for all i and they're all pairwise incongruent

In particular I am trying to see why the "it follows that" in this theorem is true

[west glade]

well that set is such a direct product

[junior swallow]

I'm sorry I don't understand

Are you saying that {1, -1} x {5^b | 0 \leq b < 2^{l - 2}} = U(Z/2^lZ)?

Wait are reduced residue systems equal to the units of Z/nZ

[kindred fulcrum]

Yes

[junior swallow]

Well I guess there are \phi(n) of them and they're all relatively prime to n...

Ah okay, thanks

[left fable]

x= 2, 5, 8
the equation is 3x = 6 + 9y or x = 2 + 3y so x =2 (mod 3)
no inverses

3 solutions

or 1 solution, depending how you look at it

[tulip vortex]

Does anyone know a "fun" proof for the value of zeta(2k) ?

[west glade]

this seems promising at least https://arxiv.org/abs/1209.5030

havent read it

see also its reference [2] I suppose

[zealous thorn]

So the big number is 123456789101112...99

My brain sayd

10000000+20000+30000+400000....something like that pattern

And by dividing it 99

(-1)+(-2)+....? Is that pattern

[warm pawn]

there are easy answers if its a summation or a product but if its just a really long integer then you need to find a trick

[drowsy jackal]

I can only think of divisibility rule of 9 and 11.
Let N=(the number)
You can write the number as
1 2 3 4 5 5 7 8 9, write the remaining digits as seperated in two columns
first column | second column
10
11
12
...
19

20
21
22
..
29

30...
99

Where digits at even places are 2,4,6,8, and then all the digits in first column and digits at odd places are 1,3,5,7,9 and then all the digits in second column of the above.

Now, sum of all odds = 1+3+5+7+9+digits in second column = 25+(1+2+..9)×9 = 25+9×10×9/2
sum of all evens = 2+4+6+8+sum of digits in first column
= 20+(1×10+2×10...9×10)
= 20+10×9×10/2

For divisibility by 9, sum of all digits must be divisible by 9

25 + 9×10×9/2 + 20 + 10×9×10/2
= 45 + 9×10×9
must be divisible by 9 which it clearly is

Let remainder when the N is divided by 99 is R, then N-R must be divisible by 99 that is N-R must be divisible by 9 and 11. We found N is divisible by 9 so R must also be divisible by 9. So options b, d eliminated.

For divisibility by 11, sum of evens - sum of odds must be divisible by 11
= -15 which isn't divisible by 11
If R=72, then second column(odd's column) will lose 2 and first column(even's column) will lose 7 as we will be checking divisibility of N-R by 11 so

new sum of evens - sum of odds
= -15 -7+2 = -20
So N-72 isn't divisible by 11 so ans must be C).

there should be ez way to do it using mod but mod isn't in my syllabus so idk but this is the intuition

-# https://www.quora.com/When-123456-99-is-divided-by-99-what-is-the-remainder found this

[sharp shadow]

My setup for studying number theory 😀

[sacred junco]

yooo

thats sick!

bro is locked in

[sharp shadow]

I was impressed by the fact that Fundamental Theorem of Arithmetics doesn't hold if you modify the numbers slightly. For example if we look at only even numbers and consider "even primes" to be numbers that cannot be further factored to even-only factors, then 60 can be factored in two ways: 60 = 2 * 30 = 6 * 10, so the uniqueness of factorization no longer holds. Another example is numbers of 4n + 1 form, or Gaussian numbers. So now I am trying to see what exactly breaks in the uniqueness proofs when we move to those numbers.

I'm moving back in the proof, lemma by lemma, noting which facts do not hold for even numbers. And got to the point where we actually define GCD, it looks like in even numbers it sometimes just doesn't exist, i.e. say 2 and 6 have no common divisors at all, since 1 is not part of our "even numbers universe"

maybe I can circumvent this and be able to go further back if I work with 4n + 1 numbers because there at least 1 is a member of that, so GCD will always by defined and we can use the same definition of "relatively prime"

[patent acorn]

well no, 2 and 6 have 2 as a common divisor

[sharp shadow]

but 2 is not a divisor of 6

in even numbers: because 6 = 2 * 3 and 3 is not even

[patent acorn]

...oh, right

[sharp shadow]

so 6 is "even prime"

[rugged locust]

yeah, those are some good observations

thinking about unique factorization is some legit number theory

[rugged locust]

unfortunately it still fails

you can group 4389 = 3 * 7 * 11 * 19 = 21 * 209 = 33 * 133 into two different ways

essentially, notice that if two numbers are both 3 mod 4 then they multiply to a number that is 1 mod 4

so if you take 4 different numbers that are all 3 mod 4 then their product can be split into 2 different ways

the core problem here, is that you can't have too many integers outside your chosen set of integers to multiply to something inside the set

once you have more than 4 then that always fails unique factorization

[sharp shadow]

ah, interesting, right this is like a different problem with GCD now.

[rugged locust]

it is essentially the same problem, actually

[sharp shadow]

that you can have several different sets to choose the maxumum from

[rugged locust]

the problem with even numbers is that non-even numbers can still multiply to even numbers

and the problem with 4n+1 numbers is that 4n+3 numbers can still multiply to 4n+1 numbers

[sharp shadow]

Right. Not clear though why it should matter, if we just restrict our attention to some set, and it is closed under multiplication...

[rugged locust]

the problem is that the factorization is external

[sharp shadow]

i.e. when we have normal natural numbers -- who cares about that there might be some crazy numbers out there that produce natural numbers if multiplied

like say I can take two gaussian numbers and multiply them and get a natural number

but somehow this doesn't cause problems?

[rugged locust]

ah, now you are talking my talk

turns out, this works because a version of the fundamental theorem of arithmetic still holds in the Gaussian integers

[sharp shadow]

ah, interesting

so are we saying that whenever we invent some numbers that give a natural number when multiplied -- then some version of FTA should hold there?

[rugged locust]

so turns out, if I give you some weird collection of numbers that is closed under multiplication (and addition), asking if a version of the FTA holds is a very subtle and very interesting question

and it's a peek into what modern number theory research actually is about

[rugged locust]

not always

turns out unique factorization is actually a "pretty hard" property for a collection of numbers to have

and "most" collections of numbers do not have it

[sharp shadow]

OK. Are there some general ways to quickly show that some collection does not have this property? Other than finding a counterexample

[rugged locust]

hahaha, yes there are some

I have no idea how to explain them easily

[sharp shadow]

is this studied in Algebraic Number Theory?

[rugged locust]

yes!

[sharp shadow]

cool 🙂 sounds interesting!

[rugged locust]

although the question people are more concerned with is showing if a collection has the property

and that's pretty hard™

[kindred fulcrum]

One nice thing is that we do have unique factorzation in a large part of these number systems, if instead looking at numbers we look at whats called fractional ideals

[sharp shadow]

is this 4 number general, or it was just something for that 4n+1 example?

[rugged locust]

well, it is this exact construction

a*b*c*d = (a*b)*(c*d) = (a*c)*(b*d)

[sharp shadow]

ah, right, I see now

[rugged locust]

you have to be a little delicate about what a,b,c,d you choose because there are some edge cases but that is the idea

[sharp shadow]

they should be kinda considered the same (i.e. both = a * b * c * d), but because we need to go outside of our set to further factor them out and make them "the same", we end up with different factorizations. An easy way to craft counterexamples! 🙂

[rugged locust]

you can, and indeed in number theory we do actually have something like that

[rugged locust]

yeah that was what I was trying to describe, you got the idea

[rugged locust]

there is a certain way in which you can identify bundles of numbers together and restore a weaker version of FTA, not for the numbers, but for the bundles

[sharp shadow]

is that something that @kindred fulcrum was alluding to above, with those ideals?

[rugged locust]

yes exactly

[kindred fulcrum]

Yes!

Dedekind domains are amazing

[rugged locust]

one of my classmates pronounces them dee-dee-kind

and at this point im half convinced they are trolling

[sharp shadow]

I vaguely remember seeing them mentionedat the end of some book, but just checked and they are definitely not in my (more elementary) physical books 🙂

[kindred fulcrum]

I learned about them near the end of my commutative algebra course

And then I learned about them in the context of number theory in my algebraic number theory course

[rugged locust]

how much was taught about them

because I was only given the basic definition and 1 lemma

and the prof essentially said that it was a problem for the NT prof to deal with lol

[kindred fulcrum]

Basic definitions, class group, properties

[rugged locust]

holy

[abstract ferry]

chad

[kindred fulcrum]

And I think some examples like integer rings, something elliptic curves

[rugged locust]

thats quite a bit lmao

[abstract ferry]

I remember a dedekind domain is UFD if and only if its ideal class group is 0 or smth

and this from algebraic geometry

[rugged locust]

i recognise that font

[kindred fulcrum]

PID even

[junior swallow]

Can somebody please help me see why this is true

I know it has something to do with the fact that 4 does not divide 5^b or 5^b'

Ok wait never mind

I don't even have to consider the preceding statement I can just see it based off of cases lol

Wait never mind I can't

This is annoying because I want to get 4 | 5^k ((-1)^a - (-1)^a')) for some k but I don't see how I can do this

Hmm maybe I should use the division algorithm and derive a contradictoin

Ah, suppose that $(-1)^a \not \equiv (-1)^{a'} ; (4)$. Then $(-1)^a = 4k + r$, $(-1)^{a'} = 4k' + r'$, where $0 < r, r' \leq 3$ and $r \neq r'$. Substituting back into the congruence, we get
[4 \mid (4k + r)5^b - (4k' + r')5^{b'} = 4(k5^b + k' 5^{b'}) + 5^b r - 5^{b'}r'] Since $4 \mid - 4(k5^b + k' 5^{b'})$, $4 \mid -4(k5^b + k' 5^{b'}) + 4(k5^b + k' 5^{b'}) + 5^b r - 5^{b'}r' = 5^br - 5^{b'}r'$. This is impossible.

[sterile pumice]

okeyokay

[versed flax]

how did you reach the last conclusion?

[versed flax]

also note here that $$(-1)^a5^b\equiv (-1)^{a'}5^{b'}\pmod{2^l}\implies (-1)^a5^b=(-1)^{a'}5^{b'}+k2^l$$\ where $k\in\mathbb{Z}$ and now consider this mod $4$ keeping in mind that $l\geq 3$

[sterile pumice]

ali yassine

[junior swallow]

Sorry I don't really see what reducing this equation mod 4 does

Don't we just get $(-1)^a 5^b \equiv (-1) ^{a'} 5^{b'} \text{ mod } 4$

[sterile pumice]

okeyokay

[versed flax]

Yes and now what can you say about 5 mod 4?

[inner tulip]

Hi

What's the doubt?

[silk tide]

@weary ivy

is 31583 divisible by 7?

7|31583 => 31583 = 7 * A where A \in Z

31583=3.1583*10⁴ => A must have at most 4 digits

the last digit of A must be 9 (A can be written as (1st digit)*10³ + (2nd digit)*10² + (3rd digit)*10¹ + (4th digit)*10⁰, when multiplied w 7 on this form u will get 1st*7*10³ + 2nd*7*10² + 3rd*7*10¹ + 4th*7*10⁰. because every other product will end in a 0 because theres a multiple of 10, the 4th digit must end on a 3 when multiplied by 7, and because the only digit for which that is true is 9, the last digit must thus be 9)

the first digit can be at most 4 (7*5009=35063 > 31593, whereas 7*4009=28093 < 31593)

the 2nd digit can be at most 5 (7*4609=32263 > 31593, whereas 7*4509=31563 < 31583)

the 3rd digit can be at most 0 (7*4519=31633 > 31583, whereas 7*4509=31563 < 31583)

the largest possible value of A is therefore 4509, but because 7*4509=31563 < 31583, 31583 is not divisble by 7

[weary ivy]

not reading all that, but sure

[silk tide]

im not sure how tight the reasoning is to begin w but it checked out to me

[kindred fulcrum]

Just do long division

[silk tide]

that would be faster, this was more of just a curiosity

[midnight wasp]

I and my friend have recently finished a paper about the function FD(n) = n * d(n) / gcd(n, d(n))^2, where d(n) is the number of divisors of n. It's been submitted to the Recreational Mathematics Magazine, and is currently in the refereeing process. I would like to post it here, in case anyone had any ideas on the conjectures we listed (or a fitting and short name for the function, because we couldn't come up with anything other than our names), or some nice generalizations and things to study about it.

The function is very interesting to me, because it behaves very similarly to the 3n+1 function from the Collatz problem, in that it jumps up and down before settling in a cycle (there are infinitely many cycles in this one).

[junior swallow]

Can somebody explain to me what this highlighted line means? Here, isn't x_1 a constant (x_1 = x_0 + bp^e)?

[kindred fulcrum]

well b is not a fixed value

or at least you want to find a value for b

[junior swallow]

Oh is it because if we find such a b then x_1 will be defined and a solution to the congruence x^n \equiv a (p^{e + 1})

[kindred fulcrum]

yeah

you try to find solutions of the form of x1

[junior swallow]

okay ty

You gotta fill in a lot of the gaps with this book

love it

[kindred fulcrum]

get ready for it, it happens a lot

in higher math in general

[junior swallow]

nah I know

i had to use lang algebra for a class so i'm well aware 😂

[red yacht]

can I get some help

idk how to solve this diophantine

39x + 48y = 135

where x,y ∈Z and x,y>=0

[kindred moss]

you can simplify it to

13x + 16y = 45

[red yacht]

yeah by dividing by gcd(39,48)

then what

[kindred moss]

13x is congruent to 45 mod 16, so you can find the inverse of 13 mod 16 to solve for x mod 16. Similarly, 16y is congruent to 45 mod 13, and you can solve for y mod 13 by finding the inverse of 16 mod 13. This gives you a much smaller set of numbers to check

[red yacht]

ok so

13x = 45 (mod 16)

then what? inverse modulo?

multiplicative inverse?

[kindred moss]

yes

[red yacht]

@kindred moss

how

[kindred moss]

there's this thing called the extended euclidean algorithm that lets you find inverses without too much difficulty

you can also just guess and reason for small numbers

[red yacht]

how to use extended euclidian

i have used it before I think, but I need a refresher

[kindred moss]

its kind of hard to explain over discord and really easy to understand from a video, it's just an algorithm

okay if youve seen it before its easier

[red yacht]

in a nutshell. how do I find the multiplicative inverse

[kindred moss]

assume x and y are relatively prime. start with x and y, and divide the larger one by the smaller one. assume x is bigger WLOG. you'll get a quotient q and remainder r. then

x = qy + r

now repeat the process with y and r. keep going until you get an equation where r is 1. then you can backsubstitute repeatedly and find coefficients a, b such that

ax + by = 1

then the inverse of x mod y is a, and the inverse of y mod x is b

[red yacht]

in this case what is X and what is Y

[kindred moss]

well, based on what i just told you, given x and y, what does the algorithm output

[red yacht]

13x = 45 (mod 16)

[red yacht]

idk, math is tough

[kindred moss]

okay x and y in my algorithm are not the x and y in the original problem

[red yacht]

yeah ik

[kindred moss]

okay then just read what i wrote

what did the algorithm find at the end

[red yacht]

idk

[kindred moss]

this isnt a trick question

do you see what I wrote?

[kindred moss]

here

do you see what's written at the end?

[red yacht]

yeah

[kindred moss]

okay

so what did the algorithm find

[red yacht]

the multiplicative inverse of 45 mod 16

[kindred moss]

did i write 45 anywhere in there

[red yacht]

i mean

the inverse of x mod y

[kindred moss]

yes

what did we want to find originally

[kindred moss]

it is here

[red yacht]

the inverse of 13 mod 16

[kindred moss]

okay

so what should x and y be

[red yacht]

13 and 16 but

can we find the inverse together step by step

is still a bit hard for me

@kindred moss

[kindred moss]

okay

so the first step, we have 16 and 13, so we divide 16 by 13

whats the quotient and remainder

[red yacht]

well

16 fits once in 13

and the reminder is 3

@kindred moss

[kindred moss]

yes

so 16 = 1 * 13 + 3

now we replace our big number with our remainder

so instead of 16, we have 3, and we keep 13

so we have 13 and 3 now

what next

[red yacht]

well

13 = 3x4 + 1

@kindred moss

[kindred moss]

amazing

and we reached 1

which was our goal

so now we can finish

[red yacht]

13 and 3 are coprime

I dont think I follow, what should I do now?

@kindred moss

[kindred moss]

13 and 3 being coprime isnt important

let me finish

[red yacht]

👂

[kindred moss]

16 = 1 * 13 + 3
13 = 3 * 4 + 1

our goal is to write 1 as a sum of multiples of 16 and 13. we will do this by substitution. start with the first equation.

3 = 16 - 1 * 13

now we have written 3 in terms of 16 and 13. we can plug this into the second equation now.

13 = (16 - 1 * 13) * 4 + 1
1 = 13 - (16 - 1 * 13) * 4

expanding, while keeping 16 and 13 there,

1 = 13 * 5 - 16 * 4

so (5) * 13 + (-4) * 16 = 1

[red yacht]

3 = 16 - 1 * 13

WTF?

@kindred moss

[kindred moss]

idk what to say to that

[glacial cove]

holy euclidean algorithm

[red yacht]

ahh I figured

you just

16 = 1 x 13 + 3
16 - 1x13 = 3

[kindred moss]

yees

[red yacht]

yes this was covered in class, is just that I am a dum dum

now we have written 3 in terms of 16 and 13. we can plug this into the second equation now.
YEAH

you have a solid grasp on the basics @kindred moss

you from america?

[kindred moss]

i guess being a discrete math tutor for 4 years paid off

yeah

[red yacht]

yeah this follows

everything good so far, is this multiplicative inverse?

[kindred moss]

yeah, 5 and 13 are inverses mod 16, and 16 and -4 are inverses mod 13

[glacial cove]

dont u just use euclidean algorithm backwards

whats the big issue

[kindred moss]

you tell me

[red yacht]

dont u just use euclidean algorithm backwards
whats the big issue
I am newbie to math, this is my first semester in university

13 = (16 - 1 * 13) * 4 + 1
1 = 13 - (16 - 1 * 13) * 4
1 = 13 - 4x16 + 4x13
1 = 13(1+4) - 16(4)
1 = 13(5) + 16(-4)

yeah this is brilliant mate @kindred moss

I HATE guessing, I prefer using extendid euclidean all the time

unless is something ultra trivial

@kindred moss

what should I do now?

[kindred moss]

thats fair

well there's actually a few things we could do from here

maybe you'll like this more

[glacial cove]

multiply by 45

[kindred moss]

yeah that is helpful

[glacial cove]

😁

oh u want them to be both positive

[kindred moss]

yeah so you have to manually adjust the coefficients a bit

which isnt the end of the world

[glacial cove]

there are like 3 options

[red yacht]

care to elaborate? yeah we need x,y >= 0

[glacial cove]

13x+16y = 45 where x,y are positive
y = 2 , x =1 should work

[red yacht]

no spoilers please

[glacial cove]

but you just look at it

3 x 16 > 45 already

so u know y = 0 , 1 , 2

like srsly

[red yacht]

you used brute force?

[glacial cove]

not much force

i mean like unless u want to do the whole euclidean algorithm thing instead of just looking at it

[kindred moss]

i think its good to see how to use it for bigger cases where you can't brute force, but it is nice to recognize when there isn't a large space of numbers to test

[red yacht]

guessing and brute forcing is not an exact science

[glacial cove]

id say 'brute force' for this question is the best way to do it

given there are only a few cases

[red yacht]

the issue is I am bad at guessing and too lazy to brute force, I prefer just use euclidean to death

[glacial cove]

i think ur supposed to find the general solution without restrictions on x, and y, and then impose these resistrictions to get a lower and upper bound for x, and y

[red yacht]

yes

I pressume

im still kinda lost on what do I need to do for this one tho

like, we were into something and then you just spoiled me the answer, so we kinda derailed a little bit on the algorithms

[glacial cove]

u have 13(5) + 16(-4) = 1
multiply both sides by 45 to get
13(225) + 16(-180) = 45

now u have a solution (225,-180)

[kindred moss]

anyway, continuing the more general method

1 = 13(5) + 16(-4)

if we multiply by 45, we get

45 = 13(5 * 45) + 16(-4 * 45) = 13(225) + 16(-180)

so (225, -180) is a solution. We can also always decrease x by 16 and increase y by 13 to get another solution, since x has a coefficient of 13 and y has a coefficient of 16, so the general solution is

(x, y) = (225 - 16t, -180 + 13t) for all integers t

from here, we can keep decreasing 225 by 16 and increasing -180 by 13, until both coefficients are positive

[glacial cove]

yeah

[red yacht]

yeah, but one is negative

[glacial cove]

yeah ik

but u can find all solutions from that one solution

as snowflake said

[red yacht]

We can also always decrease x by 16 and increase y by 13 to get another solution, since x has a coefficient of 13 and y has a coefficient of 16, so the general solution is

(x, y) = (225 - 16t, -180 + 13t) for all integers t
yes exactly

[glacial cove]

225-16t >0 and -180 + 13t > 0

[red yacht]

wait a second lads

[glacial cove]

so 180/13 < t < 225/16

i.e 13.84 < t < 14.06

so t = 14

[red yacht]

13x + 16y = 45
13(225) + 16(-180) = 45
13(-16) + 16(13) = 0

13(225 -16k) + 16(-180 + 13k) = 45

[glacial cove]

and then sub that in to get (1,2)

do u see how the 13(16k) and - 16(13k) cancel

thats why u can add 13k and 16k

[red yacht]

yeah

[glacial cove]

and u want 225-16k > 0 and -180 + 13k > 0

and that gives u a range for k

as i showed above

it gievs u k = 14

and then u sub that back in

225 - 16(14) = 1

-180 + 13(14) = 2

or u couldve just looked at the diophantine and seen (1,2)

[red yacht]

or u couldve just looked at the diophantine and seen (1,2)

I am bad at brute forcing and guessing

[glacial cove]

its okay u will get better

[red yacht]

225-16t >0 and -180 + 13t > 0
225 > 16k and 13k > 180
225/16 > k and k > 180/13
14.0625 > k and k > 13.8461538462
so k = 14

[glacial cove]

yep

[red yacht]

yeah this is better and less of a guessing strategy tbh

(x,y) = (225 -16k, -180 + 13k) with k = 14

(x,y) = (1, 2)

I appreciate the help, is just that I am not a computer to brute force every pair in Z^2 to find a solution to the diophantine equation just by looking at it

I prefer following an strategy so I can apply it to all the other exercises

I appreciate it

[glacial cove]

yeah i understand

just in this specific case u can see it pretty quickly

because there arent that many cases i hope u recognise that

45 >= 13x+16y >= 0 is quite the restriction

if x,y are positive integers

[red yacht]

care to elaborate on that?

[plain swan]

I need help on the following Diophantine equation

x^2+y^2=z^3

[glacial cove]

think about how many values of x,y satisfy that

x<=2 and y<=3

[plain swan]

I found solutions of the following form. How can I check if I found all the solutions?

[glacial cove]

very close

multiply x and y by m^3

and z by m^2

consider when gcd(x,y) = d > 1
let x = dx' and y = dy' where gcd(x',y') = 1

when u get d^2 (x'^2 + y'^2) = z^3

x' , y' ,z0 would be a primitive solution if we can relate z0 to d

and then use the parametrisation uve given

so let x' = r(r^2 - 3s^2) and y' = s (3r^2 - s^2)

and then sub in to find z0 which gives d^2 z0^3 = z^3

for this to hold we need d^2 to be a perfect cube

so d = m^3 for some m

m^6 z0^3 = z^3 => m^2 z0^2 = z^2

so u can generate them now by scaling x' and y' by m^3 and z' by m^2

so full solutions are:

x = m^3 r(r^2 - 3s^2)

y = m^3 s(3r^2 - s^2)

z = m^2 (r^2 + s^2)

[red yacht]

you can simplify it to
13x + 16y = 45
is this 16 a typo

original diophantine was: 39x + 45y = 135
we divide both sides by gcd(39,45) = 3, we get
39/gcd(39,45) = 39/3 = 13
45/gcd(39,45) = 45/3 = 15
135/gcd(39,45) = 135/3 = 45
@kindred moss

lmfao dude, dont tell me I have to do the exercise from the scratch

fuck my life dude

[kindred moss]

no

unless you wrote the problem wrong

[kindred moss]

i guess you made a typo

[red yacht]

damn

I did made a typo

FUCK my LIFE

[red yacht]

I appreciate the help though

[red yacht]

I need some help with this exercise

find when there exist, all the solutions to the following congruent equations

[glacial cove]

for ax congruent b mod k

there exists a solution if and only if gcd(a,k) divides b

so for the first one:
17x ~ 3 mod 11
gcd(17,11) = 1, which divides 3, so there is a solution

[plain swan]

I don’t think this shows that we have found all the solutions. You simply substituted r to rm and s to sm.

[glacial cove]

doesnt it?

sorry my wording mightve been off

but assume you have some solution (x,y,z)

then we can get to the primitive solutions by dividing by gcd(x,y)

[plain swan]

Ok

[red yacht]

how do I find all the tuples in Z^2 such that b = 2a (mod 5) and that 28a + 10b = 26

[wooden glen]

The integer points in 28a+10b=26 must be describable in parametric form as (p,q) + t(r,s) with t integer. First find that description. Then figure out which values of t satisfy the modular equation.

[red yacht]

I did another way but similar

---

28a + 10b = 26
gcd(28,10) = gcd(8,10) = gcd(8,2) = gcd(0,2) = 2
14a + 5b = 13
gcd(14,5) = gcd(4,5) = gcd(4,1) = gcd(0,1) = 1
using bezouts we know that
14a + 5b = gcd(14,5) exists and is solvable
lets find a solution to 14a + 5b = 1
by eye you can see (a,b) = (-1,3)
now we multiply by 13 and we get a solution to
14a + 5b = 13
so one solution is (a,b) = (-13, 39)
to find all the solutions we need to use that 14(5) + 5(-14) = 0 so
all the solutions to 14a + 5b = 13 are
(a,b)=(-13+5k, 39 -14k) with k in Z
now we need to restrict the solutions such that b = 2a (mod 5)

[39-14k] = 2[-13+5k] (mod 5)
39 -14k = [-26+10k] (mod 5)
65 = 24k (mod 5)
65 -24k = 0 (mod 5)
-24k = 0 (mod 5)
now, if 5 | 24k then 5 | -24k
so 24k = 0 (mod 5)
now notice 24 = -1 (mod 5)
so -k = 0 (mod 5)
and if 5 | -k then 5 | k
so k = 0 (mod 5)
now we know k = 5m for some m in Z
(a,b)=(-13+5k, 39 -14k)
(a,b) = (-13 + 5(5m), 39 -14(5m))
(a,b) = (-13 + 25m, 39 - 70m)

[red yacht]

this is my solution, what do you think? how you would have solved it?

[wooden glen]

Not gonna read all that, sorry.

[red yacht]

you can also use euclidian extended and get that (-1,3) is a solution to the diophantine 14a + 5b = 1
14 = 5x2 + 4
5 = 4x1 + 1
then
4 = (14 - 5x2)
1 = 5 - 4x1
so
1 = 5-(14- 5x2)
so
1 = 5 - 14 + 5x2
so
1 = 5(1+2) + 14(-1)
so 1 = 5(3) + 14(-1)

then you multiply the solution by 13 and you get a solution to 14a + 5b = 13

[red yacht]

pretty crazy how extended euclidian algorithm works

[red yacht]

I need some help with this one, i have some progress

"find all the solutions to _ that satisfy simultaneously _"

110x + 250y = 100
gcd(110,250) = gcd(110, 30) = gcd(20, 30) = gcd(20, 10) = gcd(0,10) = 10
11x + 25y = 10
gcd(11,25) = gcd(11,3) = gcd(2, 3) = gcd(2,1) = gcd(0,1) = 1
so by bezouts lemma we know 11x + 25y = gcd(11,25) exists and is solvable
so lets find a solution to 11x + 25y = 1
lets use extended euclidean algorithm
25 = 11(2) + 3
11 = 3(3) + 2
3 = 2(1) + 1

so 3 = 25 - 11(2)
and 2 = (11-3(3))
and 1 = 3 - 2(1)

so 1 = [25 - 11(2)] - [11-3(3)]
so 1 = 25 - 11(2) - 11 + 3(3)
so 1 = 25 - 11(2) - 11 + 25- 11(2)
so 1 = 25 - 11(2) - 11 + 25(3) + 11(-6)
so 1 = 25(1+3) + 11(-2-1-6)
so 1 = 25(4) + 11(-9)
11x + 25y = 1 so one solution is (x,y) = (-9,4)
now we multiply this solution by 10 so we get a solution to 11x + 25y = 10
11x + 25y = 10 has one solution (x,y) = (-90, 40)
and since 11(25) + 25(-11) = 0 all of the solutions to 11x + 25y = 10
are (x,y) = (-90 + 25k, 40 - 11k)

so this is all of the solutions to 11x + 25y = 10
(x,y) = (-90 + 25k, 40 - 11k)
now we need to restrict our solutions such that
37^2 | (x-y)^(4321)
(x-y)^(4321) = 0 (mod 37^2)

[red yacht]

the divisibility is transitive relation
37 | 37^2 and 37^2 | (x-y)^(4321)
so 37 | (x-y)^(4321)

the we can use euclids lemma
so since we know 37 | (x-y)^(4321)
yeah so since we know 37 | (x-y)^(4321)
then either 37 | (x-y) or 37 | (x-y)^(4320)
and if 37 | (x-y)^(4320) then either 37 | (x-y) or 37 | (x-y)^(4319)

and so on and so forth

so we can say that 37 | (x-y)

so coming back at this
(x-y) = 0 (mod 37)
x = y (mod 37)
(x,y) = (-90 + 25k, 40 - 11k)
-90 + 25k = [40 -11k] (mod 37)
-130 = -36k (mod 37)

-130 = -36k (mod 37)
-130 = 37q - 36k
130 = -37q + 36k
130 = 37m + 36k
130 = 36k (mod 37)
gcd(37,36) = gcd(1,36) = gcd(1,0) = 1

130 = 37m + 36k
using bezouts lemma
1 = 37m + 36k is solvable and it exist
that one solution to 1 = 37m + 36k is (m,n) = (1,-1)

130 = 37(130) + 36(-130)
130 = 36k (mod 37)
130 = 36(-130) + 37(130)
k = -130 (mod 37)
k = 18 (mod 37)
k = 37m + 18
(x,y) = (-90 + 25k, 40 - 11k)
(x,y) = (-90 + 25(37m+18), 40 - 11(37m + 18))
(x,y) = (-90 + 925m+450, 40 - 407m - 198)
(x,y) = (360 + 925m, - 407m - 158)

I want some advice, how am I supposed to tackle this one?

"Find all the a in Z for which gcd(2a-3, 4a^2 + 10a - 10) neq 1"

[wide snow]

I imagine the idea is to do the division algorithm on those two expressions

A little annoying imo, since you need some polynomial long division, but then you're instead looking at gcd(2a-3, [the remainder]), and that remainder has a lower degree, which makes things easier.

[torn kindle]

I had an idea to extend the divisor function to roots. That is you could count roots as divisors of a number and you could count divisors of roots, e.g. $\sqrt{2}$ counts as a divisor for 2

[sterile pumice]

DeRainMan

[torn kindle]

But there is a problem with this, if we allow all roots as divisors, then there are infinite divisors. So, we could limit what roots we can divide by and what roots we can divide. For example, we can say we're only going to count 1st, 2nd and 3rd roots(1, 2, $\sqrt{2}, \sqrt[3]{2}, \sqrt[3]{2^{2}}$ divides 2). Call this divisors of order 3, or for notation $d_3$(n)

[sterile pumice]

DeRainMan

[torn kindle]

Another example $d_3$($\sqrt{2}$) = 3; 1, $\sqrt{2}, \sqrt[3]{2}$

It also retains multiplicity: $d_k(\sqrt{6}) = d_k(\sqrt{2})d_k(\sqrt{3}), d_k(10) = d_k(2)d_k(5)$, for some pos integer k.

[sterile pumice]

DeRainMan

DeRainMan

[torn kindle]

You can do the same for the sum of divisors function. As for euler's totient function, it seems a bit more ambiguous and tricky

[torn kindle]

Ok, for positive integers n, totient of order k of n, $\phi_k(n) = \phi(n)(1+\sum_{m = 1}^{k}{\phi(m)})$

[sterile pumice]

DeRainMan

[kindred fulcrum]

Where does this come from?

[torn kindle]

It comes from evaluating divisor function of order k for whole numbers

But thinking about it now, it might double count roots of composite numbers that don't divide n

I think I could fix it by only evaluating the divisor function of order k of the highest prime powers for the totient function

So for ex, $\phi_k(9) = d_k(2^3) + d_k(5) + d_k(7)$

[sterile pumice]

DeRainMan

[junior swallow]

How does Proposition 4.2.4 show the forward direction of the highlighted statement? 3 is the highest power of 2 dividing 8, and a is odd, but why is x^n \equiv a (2^7) solvable?

Nvm I'm dumb we just take l = 1

[red yacht]

a = 5 (mod 6)
a = 3 (mod 10)
a = 5 (mod 8)

oh i) is just using china theorem, correct?

[kindred fulcrum]

this what you want to do yes

and its called Chinese reminder theorem, CRT in short

[red yacht]

that one, CRT

c1 = 5, c2 = 3, c3 = 5
m1 = 6, m2 = 10, m3 = 8
M1 = m2 m3 = 10 x 8 = 80
M2 = m1 m3 = 48
M3 = m1 m2 = 60

M1 y1 = c1 (mod m1)
80 y1 = 5 (mod 6)
2 y1 = 5 (mod 6)

gcd(2,6) = gcd(2,0) = 2

2( mod 6) doesnt have an inverse

a = 5 (mod 6)
<=> a = 5 (mod 3) and a = 5 (mod 2)
<=> a = 2 (mod 3) and a = 1 (mod 2)

a = 3 (mod 10)
<=> a = 3 (mod 5) and a = 3 (mod 2)
<=> a = 3 (mod 5) and a = 1 (mod 2)

a = 5 (mod 8)
a = 8k + 5
1a + 8q = 5
gcd(1,8) = gcd(1,0) = 1
1a + 8q = 1
(a,q) = (5,0)

i) a = 2 (mod 3)
ii) a = 1 (mod 2)
iii) a = 3 (mod 5)
iv) a = 5 (mod 8)

@kindred fulcrum

which congruencies can I delete

do I need the 4 of them?

[tiny hazel]

\noindent\textbf{Definition.}
A number $n$ is \textbf{irrational} if it takes more than 10 seconds to list its digits without identifying a pattern or reaching an end.
\vspace{1em}

[sterile pumice]

Altanis

[tiny hazel]

anyone wanna contest my definition of irrationality?

[red yacht]

a = 5 (mod 8) => a = 5 (mod 2) <=> a = 1 (mod 2)

[patent acorn]

i think it would take more than 10 seconds to list the digits of the rational number 2032286723164009723215283380034116162490059310463585383262401818396852787112034848343921698660486964684864104511778852703620483124463939976737089100564554474275778268378095609340858357185035015062778152041115887558350243688723798278441223595173114075045701661493275924477616985776309233327106103138859517066301077031661023014668492165136189704724712122396665965145396507798410018600034494243858951114591090501966855848581522710853545049885406839578767243796531208170054548322414638350742791999539692896177397336306983930012382120870254932343588493610594294826530345376784932506094532112457561912402180157354902640925912545236966031040677904559780490047960540371996582610077030768274861930236258698118/7635873448969540858818630110190272081503630990108818427523039960320583606270799000711659503029766884385298392584177692075928584659662847157466641053608356011685397561940904445715747704132959316789731540729790180962121629595139127227126452278021550391459027307881370845507064274771300666632023792159860489964836506333123520863666437557631244784325841779780084936413727125351320402127098016878317414637529617582834446520620163086117050810071865104648078360978752128622884602766489395230655712548506814972622263309689629253117286494882520644289797623212641303475656443313750261426553266340502211207468962889422662582821518792536844754926800196763447927700365601841538191139088759284482513701624540088251 without identifying a pattern or reaching an end

[kindred fulcrum]

maybe you are just slow to understand that there is a patern in 0.11111111111111.......

[tiny hazel]

not for a computer ❌

[patent acorn]

actually, by this definition even just most sufficiently large natural numbers are irrational, because it would take more than 10 seconds to list their digits

[kindred fulcrum]

this shows (ii) is not needed

[patent acorn]

alright then, same thing but with two random 10^100-digit numbers instead of 700-digit numbers

[tiny hazel]

[kindred fulcrum]

and using the other 3 you can use CRT to get what you want

[patent acorn]

this definition also fails in the other direction: if you're fast enough (especially if you're a computer) you can identify a pattern in the digits of the irrational number 0.101001000100001000001000000100000001... in less than 10 seconds

[red yacht]

i) a = 2 (mod 3)
ii) a = 3 (mod 5)
iii) a = 5 (mod 8)
c1 =2, c2 = 3, c3 = 5
m1 = 3, m2 = 5, m3 = 8

[kindred fulcrum]

can you not write everything here?

its a bit spammy, sorry 🙏

[red yacht]

what does this has to do with number theory

[kindred fulcrum]

rational/irrational numbers are everywhere in number theory

[red yacht]

yeah might aswell convert this into an arithmetic channel aswell

[tiny hazel]

❓

[nocturne vortex]

For part a here, do I say that $2|0, 2^2\nmid 10$ so it's only divisible by 2, or do I convert 2 to base 2 and check that $2=10|0, 2^2=100\nmid 10$ so it's only divisible by 2?

[sterile pumice]

Bottlecap Desu~(Bottlecap Gang)

[carmine tide]

yeah you can just base it off of the number of 0's at the end

[nocturne vortex]

thank you

[carmine tide]

[nocturne vortex]

one more question, my professor went over this in class saying by fermat's little theorem, assuming $2,3,7\nmid n$, we have $n^7 \equiv n \pmod{7}$, $n^7\equiv n(n^2)^3 \equiv n \pmod{3}, n^7 \equiv n \pmod{2}$. I understand the first equivalency is direct from FLT but I don't understand how the second two follow. I assume once I have this I can use Chinese Remainder Theorem to conclude along with the cases where the primes do divide n.

[sterile pumice]

Bottlecap Desu~(Bottlecap Gang)

[carmine tide]

It's a standard result that n^2 is 1 mod 3 if n is not divisible by 3

this is easy to verify by exhaustion

the mod 2 case is really just saying that n^7 and n have the same parity

which can again be verified easily through exhaustion

or you can do FLT on these as well

namely on n^2 mod 3 and n mod 2

[versed flax]

you can also say that n^7=n(n^3)^2\equiv n mod 3 by FLT

[nocturne vortex]

ah okay i understand

thank you

[junior swallow]

Shouldn't this be p^e?

[mint stone]

no, it's ok. Because am=bm(mod pm) is equivalent to a=b(mod p) if m is not 0

they just subtract a, and divide all 3 parts of the congruence by p^e

[cosmic seal]

Hi whats a recommended book for number theory?

[wide snow]

I like Eynden

Rosen is also solid

Been teaching out of those two this semester

[cosmic seal]

The proof are more intuitive or rigours

?

[wide snow]

Rosen’s a little harder core to my reading, but they’re both rigorous

(I teach nothing less!)

[cosmic seal]

Do u know a book that is more intuitive i was recommended elementary number theory by david burton but it isnt available on kindle

@wide snow

[broken phoenix]

Find the remainder $\left( 1001! \cdot 994! \right)^{19961}$ (mod $1997$) if we know that $1997$ is prime.

So we can apply Wilson here right?

$p = 1997$, $(1995)! \equiv 1 $ (mod $1997$). (I decided to use the $(p - 2)! \equiv 1 ($ mod $p)$ version because 1001+994 = 1995 so they add up nicely. But what's the next step? How do I simplify these factorials?

I could rewrite as $995\cdot 997\cdot 998\cdot 999\cdot 1000\cdot 1001\cdot (994!)^2$ but that doesn't get me anywhere.

[kindred fulcrum]

Where did the 5! Come from

[sterile pumice]

danilojonic

[broken phoenix]

from my skill issue, fixed

I noticed that $1995! = 1001!\cdot 1002\cdot 1003\cdot ...\cdot 1995$ (exactly $994$ elements after $1001!$) but I don't know what to do with that property

[sterile pumice]

danilojonic

[mint stone]

you may notice that 1995=-2, 1994=-3, ... ,1003=-994, 1002=-995 (mod 1997)

[broken phoenix]

interesting

but I don't know what to do with that fact

[mint stone]

but you wrote it yourself 1995!= 1001! * 1002 *... * 1995.

so, 1995! = 1001! * 995! (mod 1997)

[broken phoenix]

-995! = 994! (-1)?

[broken phoenix]

okay yeah I am unsure of that property

at first I thought 994! = 1995*1994...1001 because 1995 - 1001 = 994

but it seems that's a property that's not always true

that's the part I least understand here

[mint stone]

you can replace 1002 with -995 mod 1997. Similarly 1003 replace with -994. And so on.

they have equal remainders modulo 1997

[wooden glen]

So 1996! == 1001! · (995!·(-1)^995) == - 1001! · 995 · 994!

[mint stone]

yes

[mint stone]

the last one should be without minus sign

[wooden glen]

Whoops, fixed.

[mint stone]

nope, there should be no minus yet

[wooden glen]

Now the minus comes from (-1)^995, and no sign changes happen when I split 995! into 995 · 994!.

[mint stone]

you have 1996 on the left, not 1995

[wooden glen]

Yes. But what does that have to do with signs across the second ==?

[mint stone]

oh, you changed it. Ok 1996! == -1001! * 995!

[wooden glen]

And then Wilson gives us the LHS, and we only need to invert 995.
(Meanwhile Fermat deals with the silly 19961st power).

[mint stone]

yep

[broken phoenix]

yeah okay

[broken phoenix]

so what's the general algorithm for this?

take number k! = (1)(2)...(k-1)(k), rewrite as (-1)(-2)...(-k+1)(-k) and then subtract from p: (p-1)(p-2)...(p-k+1)(p-k)? Sign is decided by some (-1)^k

[mint stone]

in general, yes, you can do this. Of course it depends on the problem you want to solve.

maybe you don't need to do that at all

[broken phoenix]

but isn't that just mod number - number we want to transform?

Take the above example, 1997 - 994 = 1003 so we start from that number: 994! = 1003\cdot 1004\cdot ...\cdot 1996

which is something I noticed in the beginning but wasn't sure if it were true

[wicked roost]

Hey I can't understand this, why did you have 1996! and not 1997! or 1995!

So you used (p-1)! == -1 (mod p)?

But what if we used the (p-2)! == 1 (mod p)?

[kindred fulcrum]

same thing

[wicked roost]

I don't understand where he got the 1996! from

[kindred fulcrum]

wilson

[wicked roost]

But it wouldn't be the same

Up there he used 1996! == 1001! · (995!·(-1)^995) == - 1001! · 995 · 994!

But if we used 1995! instead we would have just 1001! 994!

[kindred fulcrum]

do the calculations carefully

that extra 1996 becomes -1

or you could say removing that 1996 doesn't remove 995

[wooden glen]

When I convert all the factors of 994! = 994·993···2·1 by negating each of them mod 1997, I first get (-1003)·(-1004)···(-1995)·(-1996). The signs combine to an overall factor of +1, and then there's 1003·1004···1995·1995 left. Together with the 1001! we already have we just need to multiply another factor of 1002 onto it, and then we have 1996! which can be handled by Wilson.

Getting 1995! instead would require us to do some extra work to get rid of the 1996 that ultimately comes from the final 1 factor in 994!

[wicked roost]

Ahh

[kindred fulcrum]

basically what tropo said

[wooden glen]

Weirdly enough, this 14-year-old question centering on essentially the above trick just showed up on the MSE front page due to an edit to one of the answers.
(Now I wonder if Bill Dubuque is here with some incognito account ...)

[sacred junco]

Lollll

[frosty ridge]

Is there a way to prove theorem of existence of primitive roots modulo p for prime p> 2

By contradiction

Construction proof is hard for me 🫠

[wooden glen]

In other words that the multiplicative group of Z/pZ is cyclic?

You can argue that if it is not cyclic -- that is, if all elements has order less than p-1 -- then there's some order n such that the group has more elements of order n than the cyclic group of order p-1 has. But that would mean that Z/pZ contains more than n solutions to x^n=1, which is not possible in an integral domain.

[wild sphinx]

a^p-1 will always leave remainder 1 with p and for any value of k which is comprime to p-1 we can find the remainder of a^k with p and show that it would be a primitive root

[wooden glen]

That seems to claim that every a is a primitive root, which is definitely not true. For a random example, try a=5, p=13. The powers of 5 modulo 15 are 1, 5, 12, 8, 1, 5, 12, 8, ... which does not cover all of the residues mod 13.

[wild sphinx]

Every a is not a primitive root; im saying every remainder formed by dividing a^k with p is a primitive root

[wooden glen]

Which is not true either.

[wild sphinx]

And yeah obviously a shouldn't be divisible by p

[wooden glen]

k=1 is coprime to 12, and 5^1 = 5 is not a primitive root.

[wild sphinx]

Oh sorry this was the way to find all primitive roots from one primitive root a 😅

[sharp shadow]

Recently it randomly dawned on me why principle of mathematical induction is kinda equivalent to the least natural number principle. I was proving something and my proof went along the lines: let's state something for f(n), and then we can lead from there to something similar for f(n-1), and eventually we go down all the way until we ran out of positive integers and then my thing was trivial to prove. Then I thought -- well, it's a somewhat strange style of proof, maybe I can just prove the same by induction, and indeed I could. And then I realised that in the first case I was actually using the least number principle! It was easier to see their equivalence in this applied setting rather than when I was reading about that in all its generality!

[graceful inlet]

Is there a simple expression for the inverse of the arithmetic function f(n) = (-1)^{n+1}/n under Dirichlet convolution?

[unique cypress]

Did you try using dirichlet series?

[graceful inlet]

Ahhhh, that seems like it would be very helpful!

[graceful inlet]

Thinking out loud: for a multiplicative function f (or at least f(2^k m) = f(2^k) f(m) for m odd), D(f) (the Dirichlet series of f) satisfies D(f) = D(f_odd) D(f_powers_of_2). Therefore D(n ↦ (-1)^{n+1} f(n)) = 2 D(f_odd) - D(f) = D(f) (2/D(f_2) - 1), so its inverse will depend on that new factor. Next, D(n ↦ f(n)/n)(s) = D(f)(s+1), so its inverse will be the Dirichlet inverse of f with the same transformation applied. Putting these together, Dirichlet inverse of (-1)^{n+1}/n = coefficients of inverse of zeta(s+1) (2(1-2^{-s-1}) - 1) = zeta(s+1) (1-2^{-s}), which is n ↦ mu(n)/n * (1_{powers of 2}) = ∑_{d = n/2^k ∈ ℤ_+} mu(d)/d = ∑_{2^k ∣ n} mu(n/2^k) 2^k/n = mu(m)/m (1 if n is odd, 1/2 if n is even), where m is the largest odd factor of n.

Hopefully that's correct.

[pseudo lark]

I am confused here with (1.13)
If we let p=3 and q=13, (p*/q)=(q/p)=1 (13=1=1^2), and so by (1.13) we should have 3 is a quadratic residue mod 4*13=52. But, it is not (I checked by hand, and consulted wolfram alpha)
does anyone have any ideas 😁

[kindred fulcrum]

notice the $\pm$ in $p = \pm \beta^2 \bmod 4q$

[sterile pumice]

ExpertEsquieESQUIE

[kindred fulcrum]

.

3 = -7^2 mod 52

[pseudo lark]

I see
Are you saying that you think it means p only has to equal beta or -beta, not necessarily both?

[kindred fulcrum]

it cant be equal to both

unless beta^2 is somehow 2q

so yeah p is only equal to one of them

[pseudo lark]

Oh yeah

Thank you ^w^

[junior swallow]

Ah okay great thanks

[silent gyro]

Hey I'm working on a project and I was wondering if there was a simple way to calculate the value of the euler totient function for values 1 less than a prime other than just brute force checking?

[kindred fulcrum]

if you know the prime factorization of n its easy to calculate phi(n)

[wooden glen]

Yes, but I don't think factoring p-1 is easy in general.

[kindred fulcrum]

Its probably not

[charred roost]

The RSA cryptosystem relies on the euler totient function being difficult to compute, so there's probably no method that's substantially faster than factoring

[tawdry sparrow]

Hi I'm working on a problem where I'm tasked to find the amount of possible values for a and b where 1 <= a,b <= 9 that satisfies GCD(10a+b, 10b+a) > 1. I have transformed it into GCD(10a+b, 99b) > 1. From this, I found that the conditions are: 3 | a+b, and/or a = b. I think the other cases are special and I need to find them manually, can anyone help me?

[sharp shadow]

nice problem 🙂 So this is basically asking to find two-digit numbers that are not relatively prime with then number when its digits are swapped. (like 27 and 72). I can see several cases when it is:

a) both digits are even (then obviously both numbers would be divisible by 2)

b) sum of digits is divisible by 3 (then both numbers would be divisible by 3 -- because if the sum of digits is divisible by 3, then the whole number is divisible by 3)

c) two digits are the same, as you pointed out

all the rest seem to be relatively prime, but I haven't proven explicitly, just looked at the remaining pairs. So my answer is || 41 ||

[sacred junco]

Problem: Given if gcd(a,b) = 1, then prove that gcd(ab,a+b) = 1.

My approach was if gcd(a,b) = 1, then no integer greater than one divides both a and b.

Let d be an integer, d>1
There are three cases:
i) d | a but d ∤ b
ii) d ∤ a but d | b
iii) d ∤ a and d ∤ b

For the first two cases, gcd(a+b, ab) = 1 is trivially true.

But I am kinda stuck at the second one where d ∤ a and d ∤ b. If d ∤ a and d ∤ b , then d ∤ ab if and only if d ≠ ab? But if d = ab, d | ab. How to proceed further?

[kindred fulcrum]

Consider when d is prime

Generally what happens if some prime p divides gcd(ab,a+b)?

[sacred junco]

Maybe if a prime number divides the gcd of a+b and ab, then the prime number must divide ab and a+b

Am I right?

[kindred fulcrum]

Yes thats the definition of gcd

what does p|ab tell you?

[sacred junco]

That there exists an integer k s.t. p | ab, or pk = ab

[kindred fulcrum]

I didn't mean the definiton 😅

There is a property of prime numbers you can use

[sacred junco]

That every integer can be expressed as a multiple of primes?

Hmm, I think I might get it.

Wait let me try it somehow.

[kindred fulcrum]

Its related to what you say here

You want p to divide one of a,b

And that is possible because p is prime

[sacred junco]

AH OKAY. SO IF p | ab then p divides one of a and b, but again if p divides one of a and b, p must divide the other as well, but gcd(a,b) = 1?

[kindred fulcrum]

Yes, try to elaborate why if p divides a or b it divides the other

Because its not something that is true on its own

[sharp shadow]

Because Euclid said so! 😄

[sacred junco]

Because p divides a+b as well and for a+b to be an integer if p divides a then p must divide b or the other way around.

[kindred fulcrum]

Yes

[sacred junco]

Yeah now, I get the proof, thanks.

But can you please check if I can prove it using my approach?

[kindred fulcrum]

Its the same thing

[sacred junco]

Almost the same, but the only difference is I didn’t consider the prime factors of d

[kindred fulcrum]

Yeah so that is what you need to do to continue

[sacred junco]

Yeah thanks, I completed the proof

[scenic echo]

hey i am doing
Olympiad Number Theory Through
Challenging Problems
Justin Stevens

and i am struggling with proofs

is this normal ?

[wooden glen]

Well, there's supposed to be struggle (it wouldn't be a competition of one could walk in from the street and do perfectly), and proofs are where the struggle is at.

[scenic echo]

yeah fair enough

[tall arch]

another way to think of it is like gcd(a,b) = gcd(a,a+b) = gcd(b,a+b) = 1, so neither a,b share any factors with a+b. Therefore, gcd(ab, a+b) = gcd(a,a+b) * gcd(b,a+b) = 1 since gcd(a,b) = 1

[scenic echo]

do we have some good video resources for olympiad nt

[tall arch]

MONT

[frosty ridge]

online math club youtube

[torpid mica]

michael penn is quite good imo but honestly nt isnt a really well talked about topic

[scenic echo]

yeah can feel it

combinatorics have lot of resources

number theory lack behind

[left fable]

what kind of number theory topics seem interesting and need more videos?

[versed flax]

What's your background? Do you know multivariable calculus and/or complex analysis? What about abstract algebra/commutative algebra?

[abstract ferry]

Galois representations

[river badger]

Can people know both analysis and algebra or they usually stick to one?

[versed flax]

Well everyone who wants to study math should know intro analysis and algebra sooner or later

Even if later on they become algerbraists or analysts or whatever

You even need to know more than intro level of both eventually ig

[abstract ferry]

everyone needs both up to some level, and for later it depends on what you want to learn

[versed flax]

But the depth would depend on the person at that point

[abstract ferry]

and usually stuffs done in undergrads are mostly these required materials

[versed flax]

I am a math undergrad
So you are still learning the prerequisites

[scenic echo]

nt proofs are so hard

or i am just too weak in proof writing

[versed flax]

Considering that you are taking elementary nt rn I can guess that it's probably the first time you do proofs

So it's normal to struggle with proofs

Also there are theorems in ent whose proofs seem to come out of nowhere at this point

So it's not really your problem

You will get used to proofs with practice

Just practice alot

[scenic echo]

practice proving stuff ?

cuz i can play with numbers

but when it come to proof

i am cooked

also where to practice ?

[versed flax]

yes

[versed flax]

pick up a textbook on the topic, say on elementary number theory, and do exercises/try to prove the stated theorems before seeing the author's proof

[scenic echo]

Ok i try

[quaint flame]

I am curious to understand what (x+y+z)^n total terms formula mean

i want to understand it with stars and bars

[scenic echo]

do you mean multinomial theorem ?

[quaint flame]

Yeah

[scenic echo]

this is wrong channel for it i guess

multinomial is part of combinatorics

this is for ele nt

i myself never understood multinomial

lol

binomial is like intuitive once you saw it

[quaint flame]

Ok

[left fable]

yea

thinking of starting a for fun channel

[left fable]

easy, he/him

qed

[cold oriole]

Hi, I think this is the right channel? Can someone tell me what mistake I made, I suspect the ln((-1)*i) = ln(-1) + ln(i) one is where it breaks down but I'm not sure

Btw WolframAlpha says the second one is correct

[rugged locust]

yep, log(ab) = log(a) + log(b) is no longer true over the complex numbers

[cold oriole]

Why not? Isn't that part of its definition, since exp(a+b) = exp(a) * exp(b)?

[rugged locust]

yes, that is still true

but the subtle thing where this goes wrong is that the logarithm is no longer a proper inverse function

since e^(2pi i) = e^0 = 1, exponentiation cannot "tell" 0 and 2pi i apart

but when you take the log of 1, it can only spit out one of the two numbers

so over the complex numbers, log(ab) and log(a) + log(b) differ exactly by a multiple of 2pi i

[cold oriole]

ahhh so it's not injective

so a proper inverse doesn't exist

[rugged locust]

exactly

[left fable]

however thats why you have "principle branches"

ie. the domain on which the function IS injective hence has an inverse

log IS the inverse, but only on a smaller domain

[cold oriole]

Truee and now I see how in the first solution, the exponent is just the second -2pi

[rugged locust]

yes!

-2pi i, you mean

[cold oriole]

yes

[cold oriole]

I'm having one of theose moments where everything just comes together, thank you very much 👌

[left fable]

btw merry, sqrt( -1 * -1) youd say is sqrt(1) = 1
but we conventionally choose the positive root, so we dont really say sqrt(1) = -1. the sqrt function as used gives the positive answer

but thats where inverses fall apart in complex analysis stuff
sqrt( (-1) (-1)) = sqrt(-1) sqrt(-1) = i * i = -1

uh oh.... 1= -1?

[cold oriole]

Ye, ik that, though did I use that here?

[left fable]

nothing is wrong here, theres no trick

no no just saying when you use complex and inverses

thats usually where an error will be

just for a hunch next time

[cold oriole]

Ah ok, thanks!

[left fable]

not guaranteed, but no longer something to say f(f-1 ( x) = x

its not that cut and dry anymore

[cold oriole]

Yee I like toying with complex numbers, and I do make that mistake a lot

[cold oriole]

Well, as long as f is injective, it should work

[left fable]

right right but then you get into domains and principle branches

like x^2 also has an inverse its injective

[cold oriole]

Which isn't the case with exp over complex numbers, but over the reals

[left fable]

just.... R+ to R+, f(x)=x^2

yes, e^x is injective! just.... on R

[cold oriole]

Ye, or [-pi/2, pi/2] to [-1,1] with sin(x)

Alr, thank you very much! Have a nice day

[left fable]

also not to yuck your yam but complex analysis sucks

the only true life style is math with integers

[rugged locust]

lmao, found the number theorist

[kindred fulcrum]

its one of the better things in math

[left fable]

we walk in strides we count in strides 🙏 🙏 🙏 🙏

[kindred fulcrum]

number theory is heavily reliant on complex analysis

[rugged locust]

I know

I was thinking about the algebraic stuff

[kindred fulcrum]

even that is reliant

[rugged locust]

realised the joke doesnt work one (1) second after I posted it

whatever man lol

[kindred fulcrum]

I am not angry

[left fable]

integrally angry

[versed flax]

You seem to hate complex analysis from one of the recent messages you sent. In that case maybe pick up a textbook on algebraic number theory (instead of something like analytic number theory) if you haven't done that yet

[left fable]

lol what

[versed flax]

?

[versed flax]

I interpreted this as you wanting to study interesting stuff in nt so I sent my message. Idk if it sounds weird lmao

[left fable]

oh buddy, read the context

its a response to someone else

wondering what kind of videos other people wish there were more of

also the hate complex and saying only integers is life is just humor, in an elementary number theory channel

lotta missing context here imo

[versed flax]

Yeah seems like that lol

[junior swallow]

Could I have a hint for this problem please

I am assuming for contardiction that $3^{p - 2} \equiv 1 \text{ mod } p$

[sterile pumice]

okeyokay

[rugged locust]

you can actually do better than that, the multiplicative order of 3 has to divide phi(p)

but phi(p) is exactly 2^n

so the order of 3, whatever it is, has to be a power of 2

[junior swallow]

Oh ok thanks, I exceeded the alloted time for this question so I'll come back to it

if a is a primitive root mod p, then a is congruent to -1 mod p right

wait naw

I'm confused what they mean by ml? What is "the" least residue? I thought least residues were a set?

Oh do they mean quadratic residue? If so, then what on earth do they mean by the plus minus sign

Maybe I'm dumb but I don't know what residue they're talking about here

[rugged locust]

no, la is going to have some representative element in the set of least residues

that representative may or may not be negative

we want it to be positive so we throw on a correcting plus minus 1 at the start

[mint stone]

no, residue means just an element mod p

[junior swallow]

Ah okay thanks

[mint stone]

in this case you can represent any number congruent to la in this form.

say if la=18 (mod 23). then m=5.

and 18=-5 (mod 23)

if la=5 (mod 23) then m=5 too

any residue modulo p can be represented as +-m, where 0<=m<p/2

if p is odd of course

[junior swallow]

Ah so in this case m_i = 5 and we add on a - sign?

[mint stone]

if remainder la mod p is in the second half you choose m<p/2 and use - sign

if la mod p is in the first half of [0;p-1] then you just leave it as a remainder

[junior swallow]

Ah okay got it thank you

[soft saffron]

Find the whole set of solutions of the equation 144x+96y=-36 where x and y are integers, can anyone help plsssss

[lilac bronze]

Try doing some factoring first

So that you can cancel common factors

[soft saffron]

😭

well 48 is a common factor

but it wont work then

can i just divide by 2

[wooden glen]

48 wasn't a factor of -36 last I checked.

[soft saffron]

yes

i simplified and got 12x+8y=-3

[wooden glen]

Which is quite easy to solve.

[soft saffron]

yea a lot easier

[soft saffron]

but

12x+8y=-3 has solution if and only if 4 | -3

[wooden glen]

Right.

[soft saffron]

so no solutions

dang

so the set is emptyset

alr

[wooden glen]

Yes.

[soft saffron]

thankss

[red yacht]

I need some help

With fermats little theorem

[sterile pumice]

Renato

[red yacht]

Like, since 6p divides this then 6 and p divides this

From there we get that 6 is just 2 times 3, so this is divided by 2 and by 3

So every term is divided by 2 that is not new info

What about 3?

[dusty dragon]

since you know that 3 | 2 * 45^{p^2 + p - 1} + 12p, we must have that 3 | (2 * 17^{p + 1} - 374), using the fact that, if a | (b + c) and a | b, then a | c

[mint stone]

Just use it. a^p=a (mod p), So, if p is not 2 and 3 the whole thing equals 2 * 17^2+2 * 45 -374 = 294=2 * 3 * 7^2 mod p. So p can only be 7. Divisibility by 6 holds automatically. The cases p=2,3, that is divisibility by 12 and 18, should be checked separately (||and they don't divide||)

[red yacht]

Can we use modular arithmetic

[junior swallow]

Could I have a hint for this problem please

I know that there are \phi(p - 1) primitive roots mod p

But I don't think they're all congruent to -1

[wooden glen]

Is p prime?

[junior swallow]

Yeah

[wooden glen]

Note that if a is a primitive root, then a^-1 (mod p) is also a primitive root.

[junior swallow]

Oh is it because (a^{-1})^{p - 2} = a?

[wooden glen]

No, because a · a^-1 = 1

[junior swallow]

Well my reasoning was that $(a^{-1})^{p - 1} = 1 \implies a (a^{-1})^{p - 1} = a \implies (a^{-1})^{p - 2} = a$

[sterile pumice]

okeyokay

[wooden glen]

Perhaps I'm just tired, but I can't follow your direction.

[junior swallow]

Anyways, I think I got it following your hint: since $a \cong a^{-1} \text{ mod } p$ for all primitive roots $a$, we must have $a_1 \dots a_{\phi(p -1)} \cong (-1)^{\phi(p - 1)} a_1 \dots a_{\phi(p - 1)} \text{ mod } p$, which in turn implies that $a_1 \dots a_{\phi(p - 1)} \cong (-1)^{\phi(p - 1)} \text{ mod } p$

[sterile pumice]

okeyokay

[junior swallow]

Oops replace all \congs with \equivs lol

[junior swallow]

Hmm I'll sanity check

[wooden glen]

a and a^-1 are generally not congruent.

[junior swallow]

Oh my reasoning was that since all the a_i are primitive roots and a_i^{-1} are primitive roots then they must the two sets {a_i} and {a_i^{-1}} must be equal, hence their products must be equal (and hence congruent)

[wooden glen]

What I was trying to say was that when you're multiplying all the primitive roots together, then each of them cancels out its inverse, except if you have a primitive root that's its own inverse.

And the only elements that are their own inverse are 1 and -1, which are not primitive roots except in the special cases of p=2 or p=3.

[junior swallow]

I'm also still trying to see why just a x a^{-1} = 1 implies that a^{-1} is a prim root lol

[wooden glen]

It doesn't.

It's still true for all the primitive roots, though.

[wooden glen]

Ah sorry, now I see what you're getting at. I moved too fast, sorry.

[wooden glen]

Yes, this is a possible argument that a^-1 is a primitive root,

You could also say that in any group, g and g^-1 always generate the same subgroup -- in particular in the multiplicative group mod p.

[junior swallow]

Oh okay yeah I forgot about that

[junior swallow]

Anyways thanks I'll think about this

Can somebody explain to me more how mu is defined? For instance, isn't 3 x 4 = 12 congruent to 5 mod 7? Why did they choose a negative representative for 12, but not for 2 x 4 = 8?

For instance, couldn't we say that 4 is congruent to 4 mod 7, 8 is congruent to 1 mod 7, 12 is congruent to 5 mod 7? What enables us to make this choice or rather what do they mean by "negative least residue" is my question I guess

Well I'm going to use Wikipedia's definition which is probably equivalent but makes more sensee to me

[mint stone]

every number mod p can be represented by one residue from the set S. So, mu is a number of 'negative' residues in S for numbers 1 * a, 2 * a, ... (p-1)/2 *a

[red yacht]

Since when is a^p congruent to a (mod p)

[mint stone]

since the dawn of time )

[red yacht]

Is that little fermat?

[mint stone]

yep

[red yacht]

Ok do you have the Def at hand?

[mint stone]

def of what?

[red yacht]

Little fermat

[mint stone]

from google

[sterile pumice]

mathrie

[junior swallow]

Oh, is this because if we look at the subgroup that the element generates and if its own inverse, then its order is 2, which must divide p (so that p = 2)

[wooden glen]

That looks valid.

(With another special case for 1).

[junior swallow]

Right

Perf thanks

[wooden glen]

Wait, no. It must divide p-1, not p.

[junior swallow]

Sorry why?

Oh because we're viewing it in U(Z/pZ), which has order p - 1 right

[wooden glen]

yeah.

[junior swallow]

Wait but the statement that a_i is not its own inverse mod p if its a_i \neq 1 and p \neq 1 or 2 is still true tho right

We may assume that $p > 3$ (these cases are proved by inspection). Let $a_1$, $a_2 \dots a_{\phi(p - 1)}$ be the primitive roots of $U(\mathbb{Z}/p\mathbb{Z})$. Now, $a_i^{-1}$ is a primitive root for all $i$; indeed
$(a^{-1})^{p - 1} \equiv 1 \text{ mod } p \implies (a^{-1})^{p - 2} \equiv a(a^{-1})^{p - 1}\equiv a \text{ mod } p $. Moreover, $a_i \not \equiv a_i^{-1} \text{ mod } p$, for if so, $\mathbb{Z}/p\mathbb{Z}$ would have a subgroup of order $2$ (which is impossible if $p \neq 2$). Thus
[a_1 a_2 \dots a_{\phi(p - 1)} \equiv 1 \equiv (-1)^{\phi(p - 1)} \text{ mod } p] since $\phi(p - 1)$ is even if $p > 3$. This completes the proof.

[sterile pumice]

okeyokay

[junior swallow]

Oh wait no this is wrong

I guess a better argument would be that if an element were it's own inverse it would generate a group of order 2 in U(Z/pZ) which is impossible if p > 3 and the element is a primitive root

[junior swallow]

Oh so basically for each number 1a, 2a, ... (p - 1)/2 a we check to see if its congruent to any of the negative residues in S, and if so, increase mu by one

[mint stone]

yep

[junior swallow]

got it thanks

Can somebody help me see why this highlighted line is true?

Oh wait, it's because here we're just taking a = 2, and an element in that set has a negative residue if it exceeds (p - 1)/2 by the definition of S

[mint stone]

It's true for any a. Doesn't matter if a=2 or not

aww, I mean mod p. Yes, for a=2, it doesn't matter bc 2(p-1)/2<p

[lilac bronze]

<@&268886789983436800>

[wooden glen]

Auto-cleanup is really slow tonight.

[hollow ruin]

I deleted that one manually

it seems to have just not triggered in this channel for some reason

[lilac bronze]

-# I haven’t received this much moderator attention for a while

[red yacht]

I need some help

[sterile pumice]

Renato

[red yacht]

i simplified the expression a bit

w23 = w5

w19 = w1

w12 = w3

w-21 I think its w6?

after that, because they are saying w is not 1 i am thinking maybe using geometric series

and because they are saying is purely imahinary, then it might be possible that the argument is either Pi/2 or 3pi/2

that is what I tried

[red yacht]

well is unclear how to continue

[west glade]

a way to find out that a number is real is to conjugate it and check whether you get the same thing back

think about a similar thing that could be used here

[mint stone]

that's easy as w-1/w is always purely imaginary for the root of unity w@red yacht

[west glade]

lets remember !nosols

[junior swallow]

Could I have a hint for this problem please

Here, u is the mobius u function

Hmm.. well I wrote $p - 1 = q_1^{e_1} \dots q_t^{e_t}$ and am supposing that $e_i > 1$ so that $\mu(p - 1) = 0$. Since $\mathbb{Z}_p$ has primitive roots it follows that there is a subgroup of $U(\mathbb{Z}_p)$ of order $q_i^{e_i}$....

[sterile pumice]

okeyokay

[mint stone]

This can be done with Moebius inversion. If d is any divisor of p-1, then you can define two functions T(d) and S(d) in the following way.
Let T(d) be the sum of all elements in (Z/pZ) * , whose orders divide d. There are d such elements and they are exactly the roots of the polynomial x^d-1 mod p (can you prove it?). So, by Vieta's theorem we have
T(d)=0 mod p, if d>1 and
T(d)=1 mod p, if d=1.
Now, let S(d) be the sum of all the elements whose orders are exactly d.
Then we have T(d)=sum S(d1) over all divisors d1 of d.
So, we use Moebius inversion and get that S(d)=mu(d) mod p. In particular S(p-1)=mu(p-1).

[onyx vale]

Guys I am new to number theory what should I start with

First

[quaint gate]

with the first chapter...

[junior swallow]

Can I have a hint for this problem

[mint stone]

just sum up an arithmetic progression

[junior swallow]

Let $a$ be a primitive root. Then $(p - 1) (p - 2) \dots 1 \equiv a^{1} a^{2} \dots a^{p - 1} \equiv a^{\sum_{i = 1}^{p - 1} i} \equiv a^{p(p - 1)/2} \text{ mod } p$. This is what I've thought of so far but I'm stuck from here

[junior swallow]

What is an arithmetic progression

[sterile pumice]

okeyokay

[mint stone]

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

[wooden glen]

It's hard to know "another proof" than what, but most likely "the existence of a primitive root" is supposed to mean that the multiplicative group is cyclic and therefore you can reinterpret the product in WIlson's theorem as summing the elements of Z/(p-1)Z.

[junior swallow]

Ah so is my reasoning correct so far

I guess I'm stuck on why a^{p (p - 1)/2} is congruent to -1 mod p.

$a^{p (p - 1)/2} = a^{(p - 1) \cdot p/2}$ though

[sterile pumice]

okeyokay

[mint stone]

then apply Fermat's little theorem and a fact that if x^2=1 (mod p) then x=1 or x=-1 mod(p)

[wooden glen]

Since p is odd the exponent is speficically the product of the integers p and (p-1)/2, and you can eliminate a^p by Fermat's little theorem.

[junior swallow]

Uh what am I doing wrong here? $a^{p(p - 1)/2} \equiv (a^p)^{(p - 1)/2} \equiv 1^{(p - 1)/2} \equiv 1 \text{ mod } p$

Did I forget my exponent rules 😂

[sterile pumice]

okeyokay

[mint stone]

a^p=a (mod p)

[junior swallow]

Ohhh yeah

Okay thanks all i got it!

It suffices to work in Z_n for this question right

Nvm

Suppose that $\langle a \rangle = G$. Then $a^{j} = g$ and $g^{k} = a$ for some $k$, $j \in \mathbb{Z}$. Thus $g^{kj} = g$ so that $kj \equiv 1 \text{ mod } n$. Thus $k$ is a unit mod $n$ and is therefore relatively prime to $n$. Does this work?

[sterile pumice]

okeyokay

[junior swallow]

Could I use the chinese remainder theorem here?

[rugged locust]

you can if you want to

[junior swallow]

I mean I feel like this is one of those intro to algebra course type problems where it involves something simple

I've only thought about this for like 10 minutes tho so it's probably elementary

How does Theorem 1 imply this highlighted line

We have $(p/q)(q/p) = (-1)^{(p - 1)/2 \cdot 2k + 1}$ if $q = 4k + 3$ but where do you go from here

[sterile pumice]

okeyokay

[junior swallow]

I'm guessing this is just by cases

Note that $(p/q) \neq 0$ since $q \nmid p$ (for $q$ and $p$ are distinct primes). Thus $(p/q) = \frac{1}{(p/q)}$. By Theorem 3, $(p/q)(q/p) = (-1)^{(p - 1)/2}$. Dividing both sides by $(p/q)$ yields the desired result.

[sterile pumice]

okeyokay

[rugged locust]

q == 3 mod 4 iff (q-1)/2 is an odd integer

[tender shell]

Is there just a section for matrix math

[quaint gate]

#linear-algebra

[tender shell]

Thanks

[junior swallow]

My thought is that A/<a> x A/<b> is isomorphic to A/<ab> and then count the cardinality of LHS

I might be trolling

[left fable]

thats exactly it, it is chinese remainder theorem

could also think about lcm(a,b)gcd(a,b) = ab

[junior swallow]

Oh yeah I knew there was a generalization to arbitrary rings

The intersection of <a> and <b> is <ab>?

[left fable]

and the image of (a,b) to equal identity

no, thats what im hinting at with the lcm * gcd

as you mentioned, the idea of counting elements

[junior swallow]

We claim that $A/\langle a \rangle \oplus A/ \langle b \rangle \cong A/ \langle ab \rangle$. Define $f: A \to A/ \langle a \rangle \oplus A/ \langle b \rangle $ by $a \mapsto (\overline{a}, \overline{a})$. Now, $f$ is surjective if and only if the congruences $x \equiv b_1 \text{ mod } \langle a \rangle$ and $x \equiv b_2 \text{ mod } \langle b \rangle$ have solutions for all $b_1$, $b_2 \in A$.

Hm I'm having a little trouble viewing this in Z

[sterile pumice]

okeyokay

[junior swallow]

Moreover A is a group not a ring

[left fable]

A abelian, and <a> has subgroup order m, <b> has subgroup order n, so (ab)^mn = ?
now suppose (ab)^k = identity. what do you use, e? 1? ill use e i think it standard for groups.
suppose (ab)^k = e then a^kb^k = e so a^k = b^-k but LHS is in the subgroup <a> and RHS is in <b>

so we have some element in <a> \cap <b>

next step can you show intersection is disjoint except for e?

er trivial intersection

after that, so its not random or aimless, trying to show that k >= mn. trying to find a condition on k

but from line 1, (ab)^mn = ? kinda finishes it off

[junior swallow]

Ah okay thanks

Is there some other way to do this other than trying out all the values lol

I know that they each have exactly 3 and 4 solutions

[left fable]

for the first one

(x-1)(x^2+x+1) = 0 (mod 19) so x=1 is a solution

and 2 more from the other