elementary-number-theory

[feral olive]

@smoky burrow I now know my mistake. I used to believed that a cong b mod n means "b divided with n remains a" I know know that it is WRONG and the truth is a cong b mod n means a divided with n remains b !!!

Is it true that 17 cong 7 mod 5 as 5 divides 10 = 17 - 7? It is written in my book but it seems really wrong

[exotic sparrow]

yes this is true

An equivalent definition of a cong b mod n is that n divides a-b

[feral olive]

oh nice! my book is right then! my definition of congruence was just wrong!!!

[fathom sierra]

if you wanted to restate that definition using remainders, it would be something like "if you divide a by n and b by n, you get the same remainder in both cases" @feral olive

[smoky burrow]

That seems very unlikely, though not impossible, especially if your "book" is a collection of your professors' notes or something.

But, in my experience, it's much more likely you misread or misremembered it.

[feral olive]

it is introduction to mathematical cryptography second eddition.

[smoky burrow]

If this is the definition, it's 100% correct.

And is identical to what I said.

[feral olive]

ok! nice! then 2 cong 4 mod 8 then ?

as 8 div 2 = 1 and 8 div 4 = 2

no

then no

bad example

[smoky burrow]

"n is divisible by m" (or "m divides n") means there exists an integer k such that n = k*m. That is, n/m = k is an integer. We write that m | n.

a ≡ b   (mod m)

means, per your book, that m divides a - b.

[smoky burrow]

2 - 4 is -2

8 does not divide -2

However, it's true that

8 ≡ 4   (mod 2)

1. 8 - 4 is 4
2. And 4 is divisible by 2

[feral olive]

ah then yes it is congruent !

[smoky burrow]

17 ≡ 7   (mod 5)

because

1. 17 - 7 = 10
2. And 10 is divisible by 5

If it helps, you can think of

a ≡ b   (mod m)
```as meaning "`a` and `b` have the same remainder after dividing by `m`", which is what @fathom sierra said.

17 and 7 have the same remainder after dividing by 5

That remainder is 2.

[feral olive]

can you explain me what is a congruence with an english sentence instead of calculation please?

[fathom sierra]

a and b have the same remainder after dividing by m
this is an english sentence afaik

[feral olive]

and could you provide me a very short math problem about congruence please?

[feral olive]

yes perfect!

[smoky burrow]

... ≡ -8 ≡ -3 ≡ 2 ≡ 7 ≡ 12 ≡ 17 ≡ 22 ≡ ...   (mod 5)

[smoky burrow]

He was quoting me, who was quoting him.

[feral olive]

17 / 5 remains 2
17 / 10 remains 7 ...

it is not coorect!!$

[smoky burrow]

what

lol

Why are you dividing 17 by 10?

[fathom sierra]

in mod 5, you always divide by 5 in a sense

[feral olive]

a and b have the same remainder after dividing by m

[fathom sierra]

2 / 5 remains 2
7 / 5 remains 2
22 / 5 remains 2
etc..

[feral olive]

yes my bad sorry

[feral olive]

please a 30 sec issue

[smoky burrow]

In general, every number that looks like 2 + 5k where k is an integer is congruent to 2 mod 5.

[smoky burrow]

Prove that a number n is divisible by 9 if and only if the sum of its digits are divisible by 9.

[feral olive]

I was asking a congruence example where I say if congruent or not before

^'

^^'

AH I might get a track

9 | n
n = 9 X a if a cong b mod 9

n = 9 X a if

a - b mod 9

if a - b mod 9 then

not finished 🙂

[smoky burrow]

Think about what "divisible by 9" means in terms of remainder

If n is divisible by 9, what is its remainder after dividing by 9?

[feral olive]

offline I wrote 9 divides n so n = 9 x X

[smoky burrow]

That's true, but what does that look like in terms of a congruence:

n ≡ ____  (mod 9)

[feral olive]

$n \equiv 9 x X (\mod 9) $

[smoky burrow]

No. What's the remainder of n after dividing by 9?

[feral olive]

it is n - x

a / 9 remains z
b / 9 remains z

[smoky burrow]

No, it's n - 9x

[feral olive]

ah no

[feral olive]

yes n - 9x <-> n ≡ 9x (mod 9)

no

[smoky burrow]

You shouldn't need to do any algebra. If "x divides y" that means x goes into y a whole number of times.

What does that make the remainder?

[feral olive]

n - 9x MOD 9 <-> n ≡ 9x (mod 9)

it is different

[smoky burrow]

What is the remainder if you divide 52 by 2?

[feral olive]

it is alway 0

there is no remained

[smoky burrow]

Yes, that's just what "divisible by" means

So "n is divisible by 9" is equivalent to

n ≡ 0  (mod 9)

[feral olive]

it implies but is not equivalent as n - 0 mod 9 is true but n - 9 mod 9 is true and n - 18 mod 9 is true as well

[smoky burrow]

Yes, every multiple of 9 is congruent to every other multiple of 9 when working (mod 9)

And they're all congruent to 0

[feral olive]

yes

[smoky burrow]

Every number is congruent to some number in {0,1,2,3,4,5,6,7,8} when working modulo 9. Those are the only possible remainders.

Which of those numbers is 10 congruent to modulo 9?

[feral olive]

is the question x congruent 10 mod 9 what is x ?

or 10 congruent x mod 9 ?

[smoky burrow]

Are those answers different?

Prove:

a ≡ b  (mod n)

if and only if

b ≡ a  (mod n)

[feral olive]

10 congruent x mod 9 then 10 - x is divisible by 9 then 9 = 10 - x multiplicate by y then 9 = 10 - 1 multiplicated by y no matter what y is

[feral olive]

is it correct?

[feral olive]

please?

[smoky burrow]

So what whole number between 0 and 8 is 10 congruent to, modulo 9?

[feral olive]

1

[feral olive]

ah no$

[feral olive]

9

[smoky burrow]

I'm stepping away. Good luck!

[feral olive]

9, 18, 27

[feral olive]

I fully understand 😕 sorry for wasting your time thanks for trying.

[feral olive]

Could I ask again next week please? I will more likeluy have progressed

there is also an english barrer

[edgy cedar]

3 | 9 means 9 is divisble by 3 or divisor of 9?

[torn escarp]

it means "3 divides 9"

so both interpretations are correct, 9 is divisible by 3 and 3 is a divisor of 9, same thing.

[feral olive]

It means 3 divides 9
And then it also means 9 is divisible by 3

[feral olive]

Yes also

[torn escarp]

sounds like you just said the same thing as me

[feral olive]

Sorry

[violet thorn]

Ask

[lethal cedar]

is there a lower bound on the kissing number for 4 dimensions?

or is it always 24

[exotic sparrow]

24 is the kissing number for 4 dimensions

https://en.wikipedia.org/wiki/Kissing_number#Some_known_bounds

[feral olive]

Hello people,

I permit me to ask you because I am looking for full answer to the exercice book An introduction to mathematical cryptrography. I found https://www.studywithus.net/sample/446sample.pdf but I do not found the answer for the question 1.15.

Did I missread something please? The answer is at https://www.studywithus.net/sample/446sample.pdf

Where is the answer to 1.15 please?

[forest plank]

Well. Let's take m=10 for example. Then we have for example 7 = 17 (mod 10) and 3 = 133 (mod 10). Is it obvious to you that 133 × 17 = 21 = 1 (mod 10) ?

[feral olive]

Thank you very very much for help. I already started to solve it at #proofs-and-logic message

I was wondering if somebody knews where is the book solution please?

[feral olive]

If you would you could get a look

[raven lintel]

#help-46 message

any help would be appreciated

i think i have to use induction

but im stuck at the induction step

[raven lintel]

ping if replying

[raven lintel]

i guess ill post it here then

given positive integers a and b, suppose that applying the euclidean algorithm leads to a sequence of positive integers $a_0, a_1, \dots, a_N$. suppose that an integral linear combination is given by $a_k = am_k + bn_k$ for integers $m_k$ and $n_k$. prove that $m_kn_{k-1} - m_{k-1}n_k = (-1)^k$ for $1 \leq k \leq N$. Then deduce that $m_k$ and $n_k$ are coprime

[sterile pumice]

syecko

[raven lintel]

i tried induction and the base was was satisfied because for k = 1 i got -1

but i didnt see how to proceed with the induction step

[forest plank]

What are a0 ... aN? There are several different sequences that euclidean algorithm generates..

Oh I guess a0 is a, a1 is b, a2 is the first remainder, and so on..

[forest plank]

Ok I think I did it

[forest plank]

Hint

[raven lintel]

thanks

[chilly pine]

How to find number of inversions of euler totient functions? for example phi(n) = 12 for 6 different numbers and how to prove it

[smoky burrow]

https://oeis.org/A002202

[chilly pine]

thanks

[hushed moat]

Can anyone help me prove this?

[exotic sparrow]

Go to #calculus

This isn't number theory

[torn escarp]

I'd work backwards from the multiplicativity of the phi function. Specifically $\varphi(p^k)=p^k-p^{k-1}$ for every prime power so you can see all the divisors of 12 have to feed into this backwards.

[sterile pumice]

Merosity

[torn escarp]

I'm in a bit of a rush but that will enable you to prove stuff, I don't think that oeis link will do much for you

[spring rampart]

can somebody help me with the second (Why?)?

[spring rampart]

I also don't get the last (why?), the third one

[vestal light]

For notational purposes, let $n = \frac{\phi(m)}{d}$. Then:

$$r^n \equiv a \text{ mod }m$$

$$(r^n)^{\frac{\phi(m)}{d}} \equiv a^\frac{\phi(m)}{d}\text{ mod }m$$

As $\frac{\phi(m)}{d}n\equiv 0$ mod $\phi(m)$, we may write $\frac{\phi(m)}{d}n = \phi(m)k$ for some integer $k$, giving us:

$$a^\frac{\phi(m)}{d} \equiv r^{\phi(m)k} \equiv (r^{\phi(m)})^k$$

Now, we clearly have that $r^{\phi(m)} \equiv 1$ (mod m), so that we have:

$$a^\frac{\phi(m)}{d} \equiv 1$$ mod m.

In the other direction, we can use basically the same algebra:

$$1 \equiv a^\frac{\phi(m)}{d} \equiv x^{\frac{\phi(m)}{d}n}$$

and as $r$ is a \textit{primitive} root, $r^\ell \equiv 1$ (mod m) if and only if $\phi(m)$ divides $\ell$

[sterile pumice]

Nathaniel Kingsbury-Neuschotz

[vestal light]

For the third (why?), just note that by the above arguments, solutions solutions to (11) are the same as solutions to (10) under the map $(\text{ind}_rx)\mapsto x$

[sterile pumice]

Nathaniel Kingsbury-Neuschotz

[sacred junco]

How would suggest I learn number theory

[exotic sparrow]

Read a book and do problems

[sharp jolt]

if n > 1 is a composite number, i am asked to show σ(n) > n + √n, where σ(n) is sum of positive divisors of n. ive been hinted that if d | n, one of d and n/d is greater or equal to √n, but i don't know how to follow up from that..

[exotic sparrow]

Notice that n divides n

[sharp jolt]

im not sure if i am getting the correct picture, but are we discarding all the terms in the sum of σ except n and one such divisor which is greater or equal to √n so that the inequality hold?

[exotic sparrow]

Well you don't have to "discard them"

But yes it is sufficient to only consider them

Also you have to consider one additional divisor (the number 1 suffices) to prove the inequality is strict

[sharp jolt]

alright i see, thank you

[forest plank]

Hmm interesting. It seems if n has d distinct divisors then $\sigma (n) > n + (d -2) \sqrt{n}$ 😊😊

[sterile pumice]

🤗🤗

[vestal light]

I realize I didn't ping you but I think I answered your questions above; let me know if any confusions remain

[red mica]

Could someone let me know if this checks out? Prove: If there are 2 integers a and b with a > b, the common divisors of a and b will also be the common divisors of a, b, and a-b. Reasoning: If q is an arbritary divisor of a and b, then there exists p1 and p2 such that p1q = b and (p1+p2)q = a, Then, p2q = a-b. Thus q will divide a-b.

[loud maple]

Yes

[red mica]

alr thx

[lethal cedar]

the function f(n) = 2 is not muliplicative right

[exotic sparrow]

no

[still flare]

Why do you think it's not multiplicative?

[lethal cedar]

f(n) = 2, f(m) = 2, so f(n)f(m) = 4, but f(nm) = 2

right?

and 2 =! 4

[still flare]

Right, for any choice of n and m, so you can easily choose specific n and m to make a counterexample

Yes, this is correct reasoning, and you are right

[lethal cedar]

ok great thank you for your help

[lethal cedar]

when we solve for say x^2 = a (mod 3) and we want to find all a's

why is it that we only need to check x = 0,1,2

does this mean that suqaring each term of a complete residue system gives us back a compelte residue system back?

[still flare]

No, squaring will not give you a complete residue system

But any example will have the value of one of the residues

so you only need to check the residues.

[lethal cedar]

im sorry but how do we know this

[still flare]

Every number

[lethal cedar]

by squaring is it not possible to lose infromation?

[still flare]

No

OK

What does it mean to be a complete system of residues?

[lethal cedar]

each element is a class and it partitions Z

[still flare]

So let's choose any number x and calculate x^2 = a. Note I am not saying mod 3 yet.

Now let's say I have some number y and I do the same thing, I get y^2 = b

Now I'm going to now imagine that x = y (mod 3)

What does this tell us about a and b?

[lethal cedar]

a^2 = b^2 (mod 3)

[still flare]

You went too far

[lethal cedar]

oh

[still flare]

It does tell us that, but in particular, it tells us that x^2 = y^2 (mod 3), which is to say that a = b (mod 3)

[lethal cedar]

sorry a = b mod 3

[still flare]

Yes

So now this tells us that mod 3, we get the same result no matter what thing in the class of x we choose

So if you choose any number x, you can get the same result (mod 3) if you choose its representative y in a complete system of residues, since you get y^2 = x^2 (mod 3)

So we can just look at the residues.

[lethal cedar]

ah so we took different numbers that were in the same class, and when we squared it it still gave us some other number in the same class?

[still flare]

Yes.

[lethal cedar]

i see

Im still having trouble connectin why squaring each number in the residue system can't give us back a residue system if this is true

I think i'll have to think about it for a while

but thank you for your help

[lethal cedar]

how would one solve the congruence x^2 = 4 (mod 7 ) without brute forcing it

is there a systematic method?

[loud maple]

Factorise x²-4, and use the fact that 7 is prime

[torn escarp]

I'm not sure if you're asking because you don't know that -2 = 5 mod 7 and that's the problem

[chrome bluff]

This is number theory esque. Okay, so for an integer n>=4, I want to show that for all a,b in Z a^2+ab+nb^2 can never be 2 or 3.

Note (this expression is always positive, and it is 0 only when a,b=0 and 1 only when a=+-1 b=0).
So we can ignore those cases

The issue that is bugging me is that ab can be negative...and it's really making me confused for some reason

[torn escarp]

just want to make sure, the n is on the exponent of the last term only right

[chrome bluff]

no, it's being multiplied

I guess I should have written it as nb^2

[torn escarp]

gotcha, yeah that makes sense, so many people write exponents "wrong" that way I wanted to be sure it wasn't the "correct" way lol

[chrome bluff]

I gotcha...otherwise that'd be way less interesting :p

[torn escarp]

I'm wondering if it's worth splitting into cases when n is square and nonsquare, but dunno just getting started

[chrome bluff]

Okay, so absolute value seems to help. This is trivially true if either a or b are 0.

Suppose they are not and |b|<|a|, then a^2+ab>0 and b^2n>0...so this is greater than n

Ah! if |b|>|a|, then ab+nb^2>0 and a^2>0. Moreover, b non-zero means |a| has to at least be 2, giving a^2=4, so a^2+ab+nb^2>4

[unkempt void]

a^2 + ab + b^2 >= 0 ||by considering squares or the fact it is (a^3 -b^3)/(a-b)||

Then the fact n >= 4 means we're done unless b = 0

But then we just have a^2

So really the only truly number theoretic input is that 2 and 3 are not squares, and that any positive integer is >= 1

[unkempt void]

Honestly though the fasts way to compute square roots to me is just to go through half of the numbers mod 7 (in this case)

In this case it is easier as x^2 - 4 has a clear factorisation but you won't always be so lucky

[ember spire]

i'm stuck on this problem from my number theory hw

[digital charm]

if you solve this let me know @ember spire

https://en.wikipedia.org/wiki/Goldbach's_conjecture

[ember spire]

i cant solve it

[digital charm]

it's an old conjecture

so no one has actually proven it yet

[ember spire]

why is it in my homework

[digital charm]

it's good to know that we still can't answer some of the most easy to ask questions in math

[ember spire]

so i just cant get 100% on the assignment then

[digital charm]

i would hope the professor doesn't require a proof of goldbach for a 100% haha

[ember spire]

heres the other question

that one was easier

[shell heath]

It's not quite the same thing as the exercise is for even numbers smaller than 21. @digital charm

[ember spire]

no the exercise asks if it's always true after that

i did it for the smaller than 21 part already

[shell heath]

Ah alright, that makes more sense. nvm then!

[lethal cedar]

got it thanks

[whole canyon]

next homework assignment: does the function r(s) = sum 1 to inf (1/n^s) always have zeroes with real part 1/2??

( 2 points )

[royal bear]

could someone explain why this follows from the top part?

not seeing it atm

[exotic sparrow]

Because the upper inequality only has finitely many solutions, we can pick C(alpha, epsilon) such that it has no solutions

[royal bear]

so because it's finitely many, you 'know' there is some pair that gives the smallest difference and then you can multiply by some small constant c so that that one doesnt work

hence the others dont work as well?

[exotic sparrow]

Yes

[royal bear]

i think i was ommiting the fact we know its a finite number when trying to reason with it

tysm

[exotic sparrow]

Yea that's the important part

you're welcome 👍

[feral olive]

Hello, in this exercise, I have to find x + 17 cong 23 mod 37.

Then I had to find 23 - (x + 17) = 37.

Why do i have to do b - a please ? Could you make a tiny proof qs well please?

[west glade]

in the real numbers how do you solve x+a=b ?

[feral olive]

X = b - a

[silk vine]

This "p" should instead be an "l", right?

[feral olive]

So?

[west glade]

just like how in the real numbers you solve $x+a=b$ by $x=b-a$, you solve $x+a\equiv b \bmod n$ by $x\equiv b-a \bmod n$

[sterile pumice]

Denascite

[west glade]

in both cases you are adding -a on both sides

[feral olive]

Are you sure i did not made a mistake. Sounds to be

37 = (x + 17) - 23

That is differrnt

37 = X - 5
X = 37 + 5

[west glade]

for starters, 17-23=-6

so yes sure you could also do this as 37=x-6 but what you are gaining from that

just like in the real numbers you dont solve x+a=b by first doing (x+a)-b=0 you also shouldnt do here (x+17)-23=0 mod 37

[feral olive]

Oh nice great then correct as -6 cong 6 cong 37

[west glade]

-6 is not congruent to 6 mod 37

x=37+6 is congruent to 6 mod 37

[feral olive]

Ok then

X + 17 cong 23 mod 37
(X+17) - 23 mod 37
X - 5 mod 37
X = 37 + 5 or X = 37 - 32

X = 42 or 6

[vapid needle]

hi, is it fine to ask for a check of proof correctness in this channel?

[exotic sparrow]

Yes

[west glade]

you cant get rid of the congruency sign. and again, its not -5

you can write the second line as (X+17)-23 cong 0 mod 37

so X-6 cong 0 mod 37

so X cong 6 mod 37

[chrome meadow]

Hey does anyone know any good textbooks for first year number theory and logic?? Thanks very much

[feral olive]

Then X - 6 mod 37

Then x = 37 + 6 mod 37

Then x = 6

Seems correct! 🙂

[feral olive]

Thank you very very much @west glade ! 🙂 i am going go get the next exercise.

[forest plank]

Proof seems to be correct. But kind of too long and verbose, but that's just my opinion. 🙂

Let $s = ord(\bar{r})$ and suppose for contradiction that $s < ord(r)$.

We have $r \bar{r} \equiv 1 \pmod{m}$

Raise to power s.

$(r \bar{r})^{s} \equiv 1 \equiv r^s \bar{r}^s \equiv r^s \pmod{m}$

So, $1 \equiv r^s \pmod{m}$ which is a contradiction.

[sterile pumice]

🤗🤗

[vapid needle]

thank you!

[runic walrus]

Thats ez

[runic walrus]

U can just verify if this is true bc its only between 3 and 21

4= 2+2
6=3+3
....

The goldabach conjecture is to prove this for all numbers greater than 2

[ember spire]

yeah read the second half of the problem

"is this true in general"

[runic walrus]

Oh

Yh ure cooked then

💀

[wild blaze]

what is 7 x 8

[sacred junco]

I have most of high school and undergraduate maths under my belt, could anyone mention the prerequisites and any other important concepts I need to learn before starting with number theory?

[still flare]

How could you have not started number theory if you have done most undergraduate maths??

My suggestion is just to start reading. There are no strong prerequisites to basic number theory

[silent charm]

prove that $x^4 = (c^2+d^2)(a+bi)$ has a solution in Z[i] iff $x^4=(c^2+d^2)(a^2+b^2)$ has a solution in Z, b,d are even

[sterile pumice]

mtr123

[sacred junco]

Actually, I am not following any set curriculum, and so I skipped it while self studying... 😅
Because the proof went over my head.
Ok, I'll begin with reading right away. Any recommendations??

[still flare]

There’s probably been recommended reading on #book-recommendations

[forest plank]

Classic introduction to modern number theory 😊

[silent charm]

prove that for all character $\chi \neq 1$ of $\mathbb Fp$ for any prime q it holds that:

$g(\chi)^q \equiv \chi(q)^{-q}g(\chi^q)$ mod q

I have that $q = c^2+d^2$ and $p=a^2+b^2$ primes such that b,d are even

[sterile pumice]

mtr123

[forest plank]

Well.. just write out both sides by definition..

[silent charm]

maybe im missing something but honestly I'm getting stuck

I have:

$g(\chi)^q = (\sum_{t\in \mathbb F_p} \chi(t)\cdot \zeta^t)^q \equiv \sum_{t\in \mathbb F_p} \chi(t) \zeta^{tq} $ mod q

now i was thinking that $chi(t) = chi(t)^q cdot chi(t)^-q$ and do something with that but I think im getting confused so would appreciate a bit help

[sterile pumice]

mtr123

[forest plank]

Multiply both sides by x(q)

[silent charm]

before even doing what i've done?

[forest plank]

Hmm actually..

Use x(t) = x(tq) x(q)^{-1}

After what you've done

[silent charm]

so i get $\chi(q)^{-1} \sum \chi(tq)\zeta^{tq}$ which is $\chi(q)^{-1} g_q(\chi)$ and still not what I'm looking for?

[sterile pumice]

mtr123

[forest plank]

Oh you lost the q power

x^q

[silent charm]

oh right, 1 sec

[forest plank]

And then everything here to the q power

[silent charm]

so again i have:

$g(\chi)^q = (\sum \chi(t)\cdot \zeta^t)^q \equiv \sum \chi(t)^q \zeta^{tq} = \chi(q)^{-q}\sum \chi(tq)^q \zeta ^{tq}$

[sterile pumice]

mtr123

[silent charm]

but then im still not sure why its g(\chi)^q

ain't it like g_q?

[forest plank]

Yes yes

Right side is x(q)^{-q} g(x^q)

[silent charm]

yeah but i dont see why its g(x^q)

I mean why that sum is g(x^q)

[forest plank]

Since q is coprime to p, tq runs through the whole Fp

[silent charm]

is the definition right?
so dont i get g_q(x)?

[forest plank]

No

[forest plank]

Here you have t, at

[forest plank]

There tq, tq

[silent charm]

yeah so i subtitue m into qt
so i have chi(m)^q zeta^m

but how i get rid of chi^q ? why it becomes g^q?

[forest plank]

It becomes g(x^q)

x(m)^q = (x^q)(m)

[silent charm]

so i have to do that move also and then its done?

just get the q inside?

since chi is multiplactive

[forest plank]

Well since characters are a group with pointwise multiplication operation

So there exists such character as x^q

[silent charm]

ok i think i got it, thank you very much!

hope its ok but I got a follow up question -
using what in the image, I'm trying to conclude that

$\chi_{a+bi}(q) \equiv p^{\frac{q-1}{4}}(a+bi)^{\frac{q-1}{2}}$ mod q

[sterile pumice]

mtr123

[forest plank]

What is x_pi

[silent charm]

pi is primary irreducible dividing p

[forest plank]

In what ring

Oh it's the quartic residue symbol right

[silent charm]

oh yeah 🙂

this is what you mean i guess? chi_pi(x) is that

i saw this proof, but i think there should be something simpler? @forest plank

[forest plank]

😭😭 I go sleep

[silent charm]

oh ok, was hoping to get help with that too! no problem

hopefully someone else could help!

[forest plank]

I will tomorrow as soon as I wake up

[silent charm]

not sure if it will be relevant

but thanks very much for the help!

[forest plank]

This proof is good actually

[lyric junco]

What is the probability that a random y-bit integer has an x-bit prime factor?

[vestal light]

This may be better asked in advanced number theory. While the question is simple and seems elementary, counting primes is hard and this feels like the kind of question that fits most nicely into analytic number theory

[lyric junco]

I just have to find advanced number theory!

[solid garden]

#advanced-number-theory

[hollow lichen]

Can wolframalpha solve a system of equations in Zn? i wanna check if i did something correctly

[west glade]

,w 2x+3y=0 mod 7, 3x-y=4 mod 7

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by denascite

[west glade]

seems like it

[sacred junco]

3^2 x 5 = 30

[hollow lichen]

ty, couldn't figure out the syntax for the life of me lol

i tried everything except that, incredible

[tender osprey]

one question

@everyone is this still true?

[loud maple]

You should check the current literature rather than asking us here

[surreal crescent]

what’s that notation? like tetration or smth?

[tender osprey]

yes

[limber steppe]

Hi everyone - wanted to share an exploratory worksheet I made that talks about cycles in modular exponentiation. ||(I know I made it in Word, but I do use LaTeX lol)||

Recently a friend asked me about a pattern he noticed in computing the last digit in powers. The goal was to efficiently compute a^b mod 10, and it seemed like we could just consider the exponent mod 4 without any casework.

That was a bit surprising! It ended up becoming an exploration of patterns in modular exponentiation for different moduli, and I conjectured (and proved) that we could use the Euler phi function to do it 'efficiently' for squarefree moduli.

I wrote an exploratory worksheet – it delves into some basic number theory and abstract algebra, and it guides you along my journey of discovery and proof.

Hope you enjoy and let me know how you go 😁

[minor plover]

how do you compute a fractional value in a base such as 1/4 in base 2?

[torn escarp]

pretty much the same way you would in base 10, although since 4 is a power of 2 there's a shortcut just like in base 10 there's a shortcut for 1/100 = .01

[runic walrus]

$$ 2025^x = 5^y + 2000 ^z , x,y,z \in \mathbb Z$$

[sterile pumice]

saintyzy

[runic walrus]

exponential diophantine equation

[lyric junco]

I asked this a week or so ago...

What is the probability that a random y-bit integer has an x-bit prime factor?

I believe the answer is 1/x asymptotically. We just take one minus the product of (1-1/p) for prime p going from 2^(x-1) to 2^x-1. Mertens third theorem gives us an approximation of this product up to n and so we can divide the product up to 2^x-1 by the product up to 2^(x-1) giving us ultimately an answer of 1/x

I would be very grateful if an expert could let me know if this is correct

[solid garden]

You would probably have better luck asking in #advanced-number-theory

[deep urchin]

@rugged locust sure

i am really not studying number theory

but iam tired of using binomial expansion to check for remainder

[rugged locust]

okay, there are actually a bunch of cool results in basic number theory that are really useful for problems like these, but I'll spare you the long proof so I don't think I'll mention those

[deep urchin]

so i started learning congruence modulo

[deep urchin]

ik for eg a^p-1congruent to 1 mod p where p is prime and doesnt divide a fermats little theorem iirc

[rugged locust]

yeah, Wilson's theorem and flt

ah shit the proof I wanted to tell you is more complicated than I thought

so let's not do that

anyways, the problem:

$2^{2^{2024}} \pmod 9$

[sterile pumice]

HChan

[rugged locust]

so here's the first thing to notice about modulo arithmetic:

is that if a ≡ a^n (mod b), then a^x ≡ a^x+n (mod b) for all other x

[deep urchin]

yea

[deep urchin]

wait

erm

[rugged locust]

yeah?

[deep urchin]

not sure what that meant

[deep urchin]

i broke 2024 into 2022 and 2 and found that 2^2024 congruen to 4 mod9

then not sure how they replaced 4 in power

[rugged locust]

okay scratch what I said

how about this:

first thing to notice, is that 9 is finite

[deep urchin]

yes

[rugged locust]

what that means is, if you keep multiplying 2 to itself mod 9

after at most 9 times you must have a repeat

[deep urchin]

yes it has finite number of remainders

[rugged locust]

but once a repeat happens, then that's no different as to doing nothing

[deep urchin]

okay

makes sense

0,1,2,3,4,5,6,7,8 then again 0,1,2,3...

[rugged locust]

so, for 2, we can check now that 2*2 ≡ 4, 4*2 ≡ 8, 8*2 ≡ 7, 7*2 ≡ 5, 5*2 ≡ 1 and 1*2 ≡ 2

i.e. 2^7 ≡ 2 (mod 9)

[deep urchin]

yes

wait

[rugged locust]

actually the more useful result here is that 2^6 ≡ 1 (mod 9)

[deep urchin]

2 to the power 2 is congruent to 4? i thought equal

[rugged locust]

they're the same

[deep urchin]

yeah because we can exponentiate whatever

[deep urchin]

yeah

[rugged locust]

congurence is equivalence in modulo arithmetic

[deep urchin]

how is 8x2 =7?

[deep urchin]

ohh

[rugged locust]

8x2 ≡ 16 ≡ 7+9 ≡ 7

[deep urchin]

oh so we talking in terms of mod 9

[rugged locust]

yes

[deep urchin]

yeah then ig sure we can divide and check all that

[rugged locust]

so, thing #2 to notice is that 2^6 ≡ 64 ≡ 63 + 1 ≡ 1 (mod 9)

[rugged locust]

no, in fact you cannot divide, but that's a whole other topic

so now here's an interesting question: what is 2^13 mod 9?

[deep urchin]

waitlet means

me

[rugged locust]

don't do it by multiplying 2 13 times

[deep urchin]

yea

2

[rugged locust]

right, and why is that

[deep urchin]

i did 2^6≡ 1 mod 9

2^12 ≡ 1 mod9

2^1 =-7 mod9

2^13≡-7mod9

2^13 ≡ 2 mod9

[rugged locust]

right, and so that's the essential idea!

[deep urchin]

yeah ik that multiply and addition rule

and how to break stuff up and look for ones or - ones

[rugged locust]

$2^{2^{2024}} \equiv 2^{2^{2024} \pmod 6} \pmod 9$

[deep urchin]

that makes it easier

[rugged locust]

so our next question is, what is 2^2024 mod 6

[deep urchin]

umm what how di dthat happen

2^2024 ≡ 4 mod9

then how did that come about in the power suddenly

[sterile pumice]

HChan

[rugged locust]

so, because 2^6 ≡ 1 mod 9, whenever 6 appears in a power of 2 you can take it out

that's exactly what you did in finding 2^13, right? 13 = 6 + 6 + 1

and you can ignore the 6's

[deep urchin]

yea

[rugged locust]

but then, what we're doing here is exactly just taking it modulo 6

[deep urchin]

wait let me absorb this

[deep urchin]

kind of i used the multiplication and exponentioan formula though

[rugged locust]

got it?

[deep urchin]

not really stuck

i mean im not sure why u wrote it as mod 6

[rugged locust]

so let's say we have 2^(6+2)

then it's equal to 2^6 * 2^2 = 1 * 2^2 mod 9

= 2^2 mod 9

[deep urchin]

yea

[rugged locust]

but then what that means, is that if we have 2^n where n is greater than 6

then we can just subtract 6 and it is still the same thing mod 9

[deep urchin]

u multiply 2 ^2 on both sides

[deep urchin]

yea makes sense kinda

[rugged locust]

but then, the action of "keep subtracting 6 until it is smaller than 6" is exactly just taking that number modulo 6

[deep urchin]

oh

so u obs that 2^6 ≡ 1 mod 9
2^(6k+n)≡2^nmod9
what it meant was substracting 6 till we get a numberwhich is n mod 6

[rugged locust]

2^(6k+n) ≡ 2^n mod9

not n

[deep urchin]

yeah

typo

[rugged locust]

so now, our question becomes, what is 2^2024 mod 6?

[deep urchin]

wait 1 sec

damn

cant find anything small

every exponent is blowing up

[surreal crescent]

yeah so 6 is the smallest number n such that 2^n = 1 (mod 9). so we want 2^2024 (mod 6). using the chinese remainder theorem its 0 (mod 2) and 1 (mod 3), so 4 (mod 6) which means 7 (mod 9) ?

[deep urchin]

not sure about chinese remainder theorem

[rugged locust]

No Chinese remainder theorem here, that’s a little too advanced

[deep urchin]

so

what do i use

[surreal crescent]

nah its helpful + not too advanced

around the same level as like fermat's little theorem?

[deep urchin]

ill ping tomorrow gtg sleep its 2 am

thnx

[runic walrus]

someone pls help

[deep urchin]

lemme know if u are free

[arctic prawn]

Anyone else find the case n=1 for congruence classes funny?

[still flare]

Now try the case n = 0

[sacred junco]

I want to show that $\sigma_k(n)^2 = \sum_{d|n} \left(\frac{n}{d}\right)^k \sigma_k(d^2)$ and i dont know where to start. Any hints?

[sterile pumice]

Plazzi

[sacred junco]

I know that there is a theorem about the convolution of arithemtic functions which implies the identity, but i'm not allowed to use that

[rugged locust]

What’s sigma?

[sacred junco]

$\sigma_k$ is the weighted divisor function. $\sigma_k(n)= \sum_{d|n} d^k$

[sterile pumice]

Plazzi

[rugged locust]

Here’s a useful trick to know whenever you see the sum \sum_{d \mid n}

Is that (n/d) forms a partition of the set of all integers less than or equal to n

i.e. sum_{d | n} [thing] = sum_{i = 1 to n} |{all 1 <= k <= n such that gcd(k,n) = i}| [thing]

[sacred junco]

let me think about it for a few minutes

[rugged locust]

Something like that, I’m not 100% sure it’s exactly that but that’s the idea

[sacred junco]

im not sure how that helps me. The sum gets very ugly very fast

[tame isle]

both sides are multiplicative functions of $n$ it suffices to check for the prime powers which should be doable since you can explicitly calculate $\sigma_k(p^\ell)$

[sterile pumice]

Atresh

[sacred junco]

It worked, thank you!

[forest plank]

Interesting problem. I only managed to arrive to 2x = min{y, 3z} and from here basically 2 main cases: y > 3z and y < 3z but idk how to deal with them

[sage fern]

81^a = 1 + 80^c. how can i find all the solutions?

wait nvm 81 is a square number lol it's so easy

[surreal crescent]

one easy way that is valid but u probably wouldnt allow is it just a case of catalan's conjecture (which isnt a conjecture anymore) but thats too much machinery? i mean it gives it to u immediately

Ok I found a way? But I think there’s better

(3^2a - 1)(3^2a + 1) = 80^c

Say 3^(2a) - 1 = 5^c * 2^k,
3^(2a) + 1 = 2^(c - k)

there’s a contradiction based on number of factors of 2s

and other case should be pretty similar

[bleak igloo]

I really having diffuct understanding this demonstration/creation of the Z set and the definition of subtraction. Do you guys have any material for help ?

[still flare]

If you have particular questions regarding it, you could also ask them here

[bleak igloo]

Ok, the problem is I don't understand it at all. Like, I get the cantor diagonal, but i didn't understand this "creation" of Z and subtracting

I would like to read in other places so I can understand better

[bleak igloo]

I was able to undestand dedekin cut and sqrt(2) by myself, without the class or professor.

[feral olive]

I need to proove that
a1+a2 mod m
And
A1×a2 mod m

I told a1a2 - a1+a2 = m × (a2-a1).

It is a different method. Is it true?

[lethal cedar]

You need to be more clear with your statement

What exactly is it you’re trying to prove here

[feral olive]

I wanted to proove that if a1+a2 is unit mod m then a1×a2 is unit mod m

Sorry for the ambigous question

[torn escarp]

it's false

1+0 is a unit but 1*0 isn't

[feral olive]

The book question is false?

[torn escarp]

the book doesn't say +, what you asked was different than what's written in the book

[calm hearth]

Why in primitive pythagorean triples, one of x y must be even?

x^2+y^2 = z^2 with gcd(x,y,z)=1

My prof quickly said some “mod 4” argument but i missed what he was saying

[rugged locust]

Suppose that x,y are both odd.

Let's just focus on x, it's the exact same for y

x is equal to 1 or 3 mod 4 exactly

if you square them, you'll find that x^2 must be equal to 1 mod 4

so x^2 + y^2 is equal to 2 mod 4 exactly

i.e. z is even

but if z is even, then z = 2k for some k, and z^2 = 4k^2 and we get that z = 0 mod 4, which is a contradiction

[calm hearth]

Interesting, thanks. I havent seen these arguments before cuz i havent taken an elementary number theory class

Im in algebraic number theory and im hoping its more abstract algebra but we started with this stuff

[shut steeple]

Hello, I’ve been working on a problem that involves a lot of exponentiation and modulo operations. I’ve done some research and seen that Euler’s totient function and Chinese remainder theorem might help, but I have no idea how to apply them. Is there anyone here who could point me in the right direction?

The question I’m trying to solve is 6^6^6^6^6^6^6^6^6^n modulo 1000 for natural number values of n.

[torn escarp]

idea is probably going to be something like a^b mod n you'll want to look at b mod phi(n) and repeat this up the tower of exponents

[bleak igloo]

Let 𝑋 be an enumerable set. Show that the subset is enumerable.

Could you guys help me with this exercise? I want to know what I should think / try to get the answer ?

[rugged locust]

what subset?

[bleak igloo]

F(X)

[rugged locust]

I can't read portugese, what does it say

[bleak igloo]

Let X be an enumerable set. Show that the subset F(X) = {Y e P(X) | Y is finite} is enumerable.

[rugged locust]

so here's a question. let's only consider the collection of all subsets of size n, for some fixed n

is this set enumerable?

[bleak igloo]

Yes, all finite sets are enumable

[rugged locust]

no no no

it isn't necessarily finite

I am asking for the set $S_n = {Y \subseteq X : |Y| = n}$

is S_n enumerable?

[sterile pumice]

HChan

[bleak igloo]

Yes, i think, since I can create a function Sn -> N that is a bijection ?

[rugged locust]

Create it!

[bleak igloo]

In terms like f(Sn) = a*b + ... ?

[rugged locust]

what do you mean

[bleak igloo]

For example: f(Sn) = n

[rugged locust]

but I am asking about the size of Sn

so your f should be defined on the elements of Sn

not Sn itself

[bleak igloo]

ooo ok.
S2 = {a1,a2,...an}.
That means a1 = {b1,b2}
So, example, if S2 is all subset of X such that |a1| = 2
Then
f(a1) = b1m + b2n

m,n e N

is this right ?

[rugged locust]

X does not have to be a set of numbers

so b1m + b2m might not be a number

[bleak igloo]

Ok, ill try again, just let me think a bit

[rugged locust]

here's a hint, you have to use the fact that X is enumerable somehow

[rugged locust]

because otherwise this set is NEVER enumerable if X is not enumerable

[bleak igloo]

yes! I cant just say that the function is | x | because that is not injective, rigth ?

[rugged locust]

you can't say the function is |x|, because you don't know if X is a set of numbers

what if X = {1.5, 2.5}?

then f(x) = |x| is not a function from X to N

[bleak igloo]

oo sorry, | x | I mean the cardinality of x

[rugged locust]

oh then that is correct

ok here's hint #2: what is the definition of enumerable?

[bleak igloo]

I don't get, in the construction of Sn all elements of Sn have the same cardinality

[rugged locust]

yes

but I am asking about the size of Sn

not the size of its elements

for example {{1,2}, {2,3}, {3,4}} is a set of 3 elements

but every element is a set with 2 elements

[bleak igloo]

A set that i can create a relation with the Natural that is 1 to one, so every element on set X has a correspondence in N and I can order that

[rugged locust]

okay, so that means there exists at least one f: X -> N that is bijective

so we can now do something with this f

[bleak igloo]

Ok, let me take a step back.
Sn = { Y subset X | cardinality of Y = n}

So S1 contains all subsets of X that has cardinality n and so on.
I can create a function f: Sn -> N that is bijective.
What is this function ?
Take S2 , S2 has all subset of X with cardinality of 2

[rugged locust]

yes, I want you to find this function

[bleak igloo]

Can I use the fact that I can order the elements of Sn and the function would be a function that takes the element of Sn and returns it's position in the set ?

For example Sn = { x1, x2, ...}
x1 < x2 < x3 .... xn

Is this right ?

[rugged locust]

you can't order the elements of Sn... you don't know that yet

but you can order the elements of X, and in fact order them like the integers

[rugged locust]

also, just because a set can be ordered does not mean it is enumerable. for example {x ∈ R | x > 0} is ordered, but not enumerable

[bleak igloo]

oooo ok

I really don't know

[rugged locust]

so how about this

What is the size of $A_n = {Y \subseteq \mathbb N \mid |Y| = n}$?

[sterile pumice]

HChan

[rugged locust]

(this is in fact the same as asking for the size of S_n)

[rugged locust]

but then think about this: what does each Y look like?

[bleak igloo]

the same as the cardinality of N ?

[rugged locust]

no no, for example if n = 2

then A_2 = {{0,1}, {0,2}, ... , {1,2}, {1,3}, ... , {2,3}, {2,4}, ...}

[bleak igloo]

Yes, the size of An is the same as N, no ? A_n has an infinite number of elements

[rugged locust]

infinite yes

but infinite does not mean the same size as N

can you prove that?

[bleak igloo]

no

[rugged locust]

this is the same trick you use in proving that Q is the same size as N

you list them this way:

{0,1}, {0,2}, {1,2}, {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {3,4}, ...

[bleak igloo]

OOo i didn't saw that

[rugged locust]

Now, can you prove that S_n is countable for all n?

[rugged locust]

Actually before that can you prove that this function is bijection first

(In fact you only need to prove that it is injective)

[bleak igloo]

I cant, sorry

[rugged locust]

Just show that it is injective

[bleak igloo]

Ok, wait a sec

[bleak igloo]

@rugged locust

I got this

I don't know if its right, but every number n e N can be expressed as a unique combination of the prime numbers

Wait, I think I get something @rugged locust while watching the class of another professor

[leaden stream]

that would certainly be an injection into the naturals.

[wild spruce]

hello

is it possible to speedrun Elementary Number Theory in a short amount of time?

I am thinking of cutting back on Exercises and just glancing over the results and doing bunch of examples

not ideal but the circumstances are not very favorable

[rugged locust]

which book?

[wild spruce]

Burton

[calm hearth]

is gcd(a,b) = 1 because z+x/2 and z-x/2 are rel prime?

so if something divided a and b, then they would divide a^2 and b^2

[hoary pollen]

I want to find the smallest maximal prime gap with a lower bounding prime that has at least 24 digits (in base 10)

i may need help to write a program that can calculate this exactly or approximately
(oops; sorry kiand123; I don't want to distract from your issue)

[calm hearth]

to show x^2+y^2=z^2 has at least one of xyz divisible by 5, I supposed x and y were not divisible by 5 and showed that then z must be divisible by 5

is that sufficient?

[vast dove]

For which values of n does the euler totient function phi(n) = 2?

[torn escarp]

phi is multiplicative so you can build it up out of power of primes phi(p^k) = p^{k-1}(p-1) must divide 2, so this is either 1 or 2.

I just worked it out and got three solutions to phi(n)=2 that should be all of them

interestingly it looks like it's not too much extra to solve the more general case of when is phi(n) prime

[vast dove]

Thanks mero

[torn escarp]

Yeah you're welcome Yamin

[rugged locust]

in finding all pythagorean triples, we start by assuming that we only want to look for primitive triples, because all solutions are just multiples of some primitive triple

now if d divides gcd(z+x/2, z-x/2) then d must also divide (z+x/2) + (z-x/2) = z and (z+x/2) - (z-x/2) = z, so d = 1

because we start by assuming gcd(x,y,z) = 1

[jagged narwhal]

oh a cool question

[bleak igloo]

A dificult one, will ask the professor today

[jagged narwhal]

I haven't ever seen such problem so it seems cool. I will try it today as well

[west glade]

as a hint, ||if you have seen how binary strings of length n correspond to subsets of {1,...,n}, try using that idea here somehow||

[jagged narwhal]

I have an idea as well, motivated from HChan lemme show

,texsp ||if $X$ is countable then it contains infinitely many subsets of $n$ elements for each $n\in \Bbb N$. Thus $A_n={Y\subset P(X):|Y|=n}$ is countable and $\bigcup_nA_n ={Y\subset P(X): Y \text{ is finite}}$ is countable||

[sterile pumice]

Afzal

[west glade]

||why is A_n countable||

[jagged narwhal]

Umm yeah lemme think

[jagged narwhal]

I am not certainly sure, but we can do like

,texsp ||let $Y(i_1,\ldots,i_n)={x_{i_1},\ldots,x_{i_n}}$ such that all members are distinct. Now $A_n={Y(i_1,\ldots,i_n): i_m \in \Bbb N \land i_k\neq i_j \text{ for all } j< k}$. It resembles with $\Bbb N^n$ so i guess $A_n\sim \Bbb N^n$ which is countable||

[sterile pumice]

Afzal

[bleak igloo]

What the professor did is almost that. Will pass onto paper and do the final proof that is to porrf that the union of infinity countable sets are infity

[calm hearth]

and this was Theorem 1.1

can I just use the solution in 1.1 to write x+y = a^2-b2, etc?

i feel like stuff goes wrong with parities and all this idk

Because in theorem 1.1 we have that z is odd, but 2z is not odd

I am kind of clueless with number theory atm

[jagged narwhal]

i see

[spare frigate]

yes

well investigate primitive triples
(x+y,x-y,2z)

u can divide by 2 and do casework too im p sure

[calm hearth]

in thm1.1 we get that z must be odd, but in this case 2z is always even

[spare frigate]

since x and y have the same parity

(x+y) is divisible by 2

so you can divide both sides by 4

to find a primitive triple of form ||((x+y)/2,(x-y)/2, z)||

and then you can see that the solutions to #4 are ||(a^2+2ab-b^2, a^2-b^2-2ab, 2(a^2+b^2))|| don't reveal this until u get the answer

[calm hearth]

Ok so essentially the idea is to convert it to exactly the conditions of thm 1.1

With z being odd

Because as it was in the hint, thm 1.1 couldnt be used right away as is

Is that right?

[spare frigate]

yep just manipulate it so the theorem works

[calm hearth]

Thanks. Is that kind of the “meta” of how elementary number theory works? I havent done this before

[spare frigate]

idk

maybe for this problem

[calm hearth]

Oki ❤️

[hoary pollen]

I want to find the earliest maximal prime gap with a lower bounding prime that has at least 24 digits (in base 10)

[torn escarp]

what do you mean by maximal prime gap

there are arbitrarily large prime gaps - there's a fun proof of this fact too.

[hoary pollen]

https://en.wikipedia.org/wiki/Prime_gap#Numerical_results

le 83 known maximal prime gaps (per that page)

also I wanna see some discussion on record prime gap length gaps

you read correctly — the gaps between the lengths of the record prime gaps

'cause like all of the prime gaps increase steadily by 2 until the 113-127 gap, which is a prime gap of 14, surprisingly skipping prime gap lengths 10 and 12

and I think at the 99th prime there's a gap of 18, which skips what would have been a 16-length gap

I wanna know what the most aggressive prime gap is, if we measure prime gap aggressiveness in how many prime gap lengths which are multiples of 2 have not happened yet despite being smaller than the prime gap in question

Notably Aggressive Prime Gaps — a table I want to look at

[torn escarp]

what have you tried so far

[hoary pollen]

I am utterly clueless. I know vaguely about prime sieves and that seems not very helpful for my problem.
I also considered, just the other day, checking for probable primes

[bleak igloo]

$$\text{Let } X = {x_1, x_2, ..., x_n, ...} \subset \mathbb{R} \text{ be an infinite countable set. For each } n \in \mathbb{N} \text{ define }a_n = \sup{x_i|i \geq n} \text{ and } b_n = \inf{x_i|i \geq n} \text{. Show that } a_n \geq a_{n+1}, \forall n \in \mathbb{N}$$

After slamming my head multiples times, things start to come clear in my head, but just a little bit.

[sterile pumice]

Guilhotina

[patent acorn]

Let $X = {x_1, x_2, ..., x_n, ...} \subset \mathbb{R}$ be an infinite countable set. For each $n \in \mathbb{N}$ define $a_n = \sup {x_i : i \geq n}$ and $b_n = \inf {x_i : i \geq n}$. Show that $a_n \geq a_{n+1}$, for all $n \in \mathbb{N}$

[bleak igloo]

Let X = {...} a infinite countable set. For each ....
Define:

Show that.

[sterile pumice]

bee [it/its]

[bleak igloo]

@patent acorn thanks

I was able to get a solution. Don't know if its rigth, but I was able to do on my owm

The key here is to know that $$X_{n+1} \subset X_{n}$$

[sterile pumice]

Guilhotina

[solid garden]

yes

I assume by X_n you mean {x_n, x_{n+1}, ...}

[bleak igloo]

yess

[bleak igloo]

Furthermore, show that if X is bounded above, then the set A = {aₙ; n ∈ ℕ} is bounded below. Similarly, show that if X is bounded below, then B = {bₙ; n ∈ ℕ} is bounded above.

This is the second part. intuitively I know this is true, because if X is upper bound I know that the supremum are decreasing and it must reach the lower bound that is the naturals. But I can't show in math way/terms.

Could you help me?

[rugged locust]

your text is not loading, use $...$ instead of $$...$$

[solid garden]

#elementary-number-theory message

[calm hearth]

I have q | a, q | b^2. I have that gcd(a,b) = 1 . Can I show a contradiction?

[still flare]

q=1.

So no, lol

[calm hearth]

q not 1

[still flare]

q = -1

[calm hearth]

Lol

[still flare]

If q has any nontrivial prime factors then it would have to be a common prime factor of both a and b.

[calm hearth]

oh, and a and b have no common prime factors because gcd(a,b) = 1

[still flare]

Any common prime factor of a and b is a factor of gcd(a, b), yes.

[calm hearth]

thanks, yea its funny how i havent thought too much about numbers too much before lolll

[still flare]

The gcd is the greatest common divisor in terms of the <= relation and the | relation, in other words

Kind of a nontrivial fact you have to prove when defining this thing

[calm hearth]

Why do we need to do this again? It looks like Thm 1.1 requires that xyz are pisitive, gcd(x,y,z) is 1, at least one of xy (say y) is even, and x and z is odd

So if we just had (x+y)^2+(x-y)^2=(2z)^2, this is not satisfied?

For x,y satisfying x^2+y^2=2z^2

[spare frigate]

x+y and x-y have the same parity

[calm hearth]

Yes because they satisfy x^2+y^2=2z^2

[spare frigate]

no

cus on the right we have

4z^2

not 2z^2

so like dividing by 2 is aura

[calm hearth]

Hm

Brb

If x^2+y^2=2z^2 x and y have same parity dont they

Because x^2+y^2 is even

[calm hearth]

I dont see the significance of that

[calm hearth]

Is it true that gcd(x+y,x-y,2z) = 2?

if gcd(x,y,z) = 1?

and x^2+y^2=2z^2

[torn escarp]

yeah that's right

[torn escarp]

I'm tempted to then use that with this to rewrite this:
(x+y)^2+(x-y)^2=(2z)^2
as this by factoring out the 2s:
((x+y)/2)^2 + ((x-y)/2)^2 = z^2

[calm hearth]

Does this have gcd((x+y)/2, (x-y)/2,z) = 1?

[torn escarp]

well they should if you use theorem 1.1 to pick them

[calm hearth]

Wdym?

[torn escarp]

(x+y)/2 = a^2-b^2
(x-y)/2 = 2ab
z=a^2+b^2

[calm hearth]

I thought we needed them to have gcd of 1 to use that formula

[torn escarp]

I haven't thought through if it matters if we pick the (x+y)/2 and (x-y)/2 in opposite way there but might not

[torn escarp]

gcd(a,b)=1

here we're forcing it

this is a primitive pythagorean triple when picked this way

add and subtract the two formulas to get a formula for x, y directly

we can continue from there and check though

but if ((x+y)/2)^2 + ((x-y)/2)^2 = z^2 isn't even a primitive pythagorean triple, then we're getting non primitive solutions to x^2+y^2=2z^2

[bleak igloo]

If a sequence A converges to L (L being a natural number) can I say that limit A = L and that limit A = sup(A) ?

[bleak igloo]

No, this does not make sense

For this to make sense I have to take the set of A and order it

[torn escarp]

it could be a decreasing sequence

[still flare]

The limit of a sequence is typically not the supremum of the set of its values. A sequence can “wiggle around” before converging, if that makes sense

[torn escarp]

Reason I said this was to help suggest you to come up with your own counterexample to see

although we could prove it more generally ||if lim A = sup(A) then add 1+sup(A) to the beginning of the sequence A and you get a new sequence with a higher sup than A but has the same limit.||

[patent acorn]

It only proves that the new element is absent from the listed elements. It does not prove how the new element is absent from the remaining infinite elements that were not listed.
...well, if there actually was a bijection between R and N, then there wouldn't be "remaining infinite elements that were not listed", because every element of R would be on the list, assuming that you constructed the list from the bijection

the problem with the actual construction of a bijection in that video is that if you "simply list them randomly",

1. they didn't even define what that means or prove that it's possible
2. there's no reason to expect that listing them randomly would cover every real number

so basically this video's argument is completely wrong

https://us.metamath.org/mpegif/canth.html here's a completely formal computer-checked proof of Cantor's theorem
can you show me where exactly the incorrect step is in this argument?

[bleak igloo]

Yeah, later I saw that this do not make sense, (1,1/2,1/4,...) , (an) an = (1/2)^(n-1) the sup is 1 but the limit is 0

Later I will need help with cesaro mean theorem demo:

[torn escarp]

this is really more for an analysis channel, not number theory, so try asking there instead

[bleak igloo]

what is the channel?

[torn escarp]

#real-complex-analysis is one, I believe there are others too but that's probably fine

[sterile pumice]

Aguacate

Aguacate

[still flare]

Correct, they are the same. This is a general fact about equivalence relations.

[scenic abyss]

oh

[still flare]

You sound disappointed

[unkempt void]

Prove it

[chrome meadow]

Hello

Does anyone know good textbooks for number theory + logic

[rugged vigil]

I think in #book-recommendations you'll find some answer

[timber wind]

Find the number of even dovisors of 12!

So here should i divide by 2

So i got 12/2+12/4+12/8

=10

[rugged locust]

An even divisor shouldn’t just be a power of two, it just needs to be divisible by two

If you count the number of even divisors of the numbers 1 though 10 alone you get 10 even divisors

There should be way, way, way more than 10

[torn escarp]

I'm thinking it might be best to go back to how the number of divisors function is derived, as a product of 1+powers on the prime factorization. You can count them in a similar that way but slightly changed to account for only the even factors.

[sacred junco]

Hi, I hope it's the right place to ask this question.
When solving a standard linear congruence ax \equiv b (mod c) according to my notes i can multiply both sides by a^{-1} only if gcd(a, c) = 1. Why is that? The answer is probably really simple but I'm confused. Thanks.

[west glade]

a^-1 just doesnt exist otherwise

[sacred junco]

oh ok

thanks

[still flare]

We write $a^{-1}$ to mean a number such that $a^{-1} a \equiv 1 \bmod c$. If it exists, then it's unique (mod $c$).

Experiment for a moment with the choice $a = 2$ and $c=4$, so you're looking for some number -- let's call it $x$ for simplicity's sake -- such that $2x \equiv 1 \bmod 4$. Have a think about this situation, and try to relate what happens to the fact that $\gcd(a, c) = 2$.

[sterile pumice]

$\mathbf{Boytjie}$

[sterile pumice]

Vanellope von Schmugz

Vanellope von Schmugz

[lavish river]

this seems intuitive to me but I'm just not coming up with any way to show it

I tried using Bezout's identity but I don't think that leads anywhere useful

[sterile pumice]

Vanellope von Schmugz

[lavish river]

what are adx' and bdy' here?

[sterile pumice]

Vanellope von Schmugz

[lavish river]

right. what is d in this case, and how do we know that it divides both x and y?

huh?

I was not referring to your problem

I posted a new one. can you see it?

it's all good lol

oh lol that's okay

[sterile pumice]

Vanellope von Schmugz

[lavish river]

ord_p(a) is the power of p in the prime factorization of a

i.e. the largest n such that p^n | a

[sterile pumice]

Vanellope von Schmugz

[lavish river]

for better or worse this is the notation we were given

interesting, though

anyways just a hint might be good if you know the solution. I feel like I'm going in circles and I don't think I'm picking up the arguments in number theory very well in general so far

much appreciated. take your time

[sterile pumice]

Vanellope von Schmugz

Vanellope von Schmugz

Vanellope von Schmugz

[lavish river]

my professor types up the exercises, so it may not be from a book directly

if he did get it from a book, it would probably have been Introduction to the Theory of Numbers by Zuckerman and Niven

seems like a reasonable problem to have in an intro book though. my professor writes a bit about how we could've defined GCDs in terms of prime numbers and started number theory from this perspective, and this series of problems effectively proves that the two are equivalent

hmm I'm still not sure where to move from here. what information do we get when we assume b < a? I don't think we get any information about ord_p(b) and ord_p(a)

[sterile pumice]

Vanellope von Schmugz

[lavish river]

does this require ord_p(a) < ord_p(b) for all p?

I can't see any other way this is true, but that's obviously not true in general

[sterile pumice]

Vanellope von Schmugz

[ivory cosmos]

is there a trick to figuring out if 7! + 19 is prime?

other than just computing it

[long lion]

what is ur definition of gcd?

the normal definition of gcd is that

gcd(x, y) | x and gcd(x,y) | y

and if d | x and d | y then d | gcd(x, y)

this works even for other rings where you do not have some notion of sizes

[long lion]

show that p^(min(ord_p(a), ord_p(b))) divides a and b

and that p^(mind(ord_p(a) + 1, ord_p(b) + 1)) does not divide both a and b

given ur context i'm assuming u've proved unique factorisation so that's a fact u can use

[long lion]

if this is in the context of a contest problem, if the problem is "is X prime or not" the answer is always no, you cannot prove X is prime by doing some clever trick that doesn't involve computation

for small-ish numbers like 7! + 19 it's probably just faster to compute 7! + 19, then verify that it's not divisible by any primes up to ~sqrt(7! + 19)

you can speed it up slightly by the fact that u know 2,3,5,7 do not divide 7! + 19

there are polynomial time algorithms for proving if p is prime or not

some of them are probabilistic

some of them are only deterministic if i.e. GRH is true

anyway altogether if you have to prove definitively that p is prime, for something like this just brute force it

it'll be completely overkill to try something like ^

(but lol proving GRH to use an efficient algorithm to prove that 7! + 19 is prime would certainly be...something)

[ivory cosmos]

not a contest problem 😭

[ivory cosmos]

what's GRH?

[long lion]

if you really insisted that gcd(x, y) is the largest number that divides x,y then you can use unique prime factorisation

or there's this nice proof that i found on mathstackexchange

but that uses the defn of lcm as

lcm(a,b) is such that if a | n and b | n, then lcm(a,b) | n and a | lcm(a,b) and b | lcm(a,b)

i think you're probably gonna find that all proofs of gcd will inevitably using some form of bezout

reason being that the integers are inherently an additive + multiplicative structure

it's this additive structure that gives us a lot of the nice multiplicative properties we have

unique prime factorisation is really quite special

for example, if you take all the integers that end in 1

that is closed under multiplication, so you can define like "primes" but you do not have unique prime factorisation so gcds etc. do not make sense

[long lion]

generalised riemann hypothesis

riemann hypothesis is still unsolved and has a $1m prize for proving/disproving it

generalised riemann hypothesis is a generalisation of the riemann hypothesis (so it's even stronger than riemann hypothesis)

[ivory cosmos]

😭 how does that relate to my problem

am i being dumb

i mean yeah it does but like

can u elucidate how it links thinks together?

[long lion]

oh as in some algorithms don't prove that p is prime

some just like give a high probability that p is prime

but some of these algorithms prove that p is prime if GRH is true

[ivory cosmos]

oh they do that to speed up computation ig

[ivory cosmos]

oh

[long lion]

anyway if you had to definitively prove that something like 7! + 19 is prime by hand, just compute it by hand

and test up to ~sqrt(p)

[ivory cosmos]

yeah that part i get

i was curious if there was another way to

with high certainty say it works

like those algorithms which hinge on GRH being true

[long lion]

oh if u just want high certainty there's lots of algorithms

[ivory cosmos]

would clearly work on smth like 7! + 19 right?

[long lion]

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

[ivory cosmos]

yes primality test is the

sqrt(p) thing i guess

but that isn't probabilistic, no?

[patent acorn]

"primality test" just means "an algorithm to test if a number is prime"

[ivory cosmos]

wait there are more algo's there

[patent acorn]

brute-forcing factors is an example of a primality test, but it's not the only one

[ivory cosmos]

yeah makes sense

okay then thanks

i guess a lot of things (prime related) is just a mystery

😔

[long lion]

that is the normal definition of gcd

since in i.e. Z[i], there is no notion of "size"

it is much more natural to take that as ur definition and prove results using that

i.e. gcd always exists, gcd is the "largest" when we work in Z

integers adjoin i

(so gaussian integers)

C cannot be totally ordered

while preserving i.e. multiplication etc.

[rugged locust]

erm actually, it’s still a Euclidean domain

[long lion]

lol you know what i mean

[rugged locust]

But yeah

[long lion]

had to be careful with this too cus u can totally order any set

by well ordering principle = axiom of choice

not a total ordering

cus |2i| = |2| but 2i != 2

[rugged locust]

It would work, but then you get the problem that there exists numbers a, b such that ||a|| = ||b|| but a is not equal to b

So it would require a looser meaning of what “size” is.
It’s called a Euclidean function, and Z[i] is what you would call a Euclidean domain, if you want to look into it

[patent acorn]

and also this order doesn't particularly behave nicely with addition

if |a| < |b| that doesn't tell you anything about whether |a+1| < |b+1|

[rugged locust]

If you lose a sense of size, the there exists number systems when there can be multiple numbers that satisfy your gcd condition

So, we introduce some sense of size such that there still exists a unique gcd that we can talk about

You actually see this problem in the integers already!

[rugged locust]

Let’s say d=gcd(a,b). Then technically both d and -d satisfy the gcd conditions

But we say that d > -d, so we don’t consider -d as “the” gcd

It is “a” gcd

It’s just that we’re so used to ignoring -d that most people don’t realise that this problem even exists

Exactly, it’s in the name

The greatest common divisor doesn’t exist, if you don’t know what greatest means

And sometimes there really isn’t a way to make “greatest” make sense

[rugged locust]

A la this

Yeah, and in Z it’s fine

[rugged locust]

As a final note, you can make the argument that d and -d and “the same”, and that would be correct! There is a very precise sense in which that is true. So, you could generalise the gcd function a little bit to instead refer to “the collection of all numbers that satisfy the gcd condition”

But then it no longer makes sense to refer to the gcd as “the” gcd

Actually, it is still “greatest”

In the sense that everything else that divides both numbers must divide that number

So it’s the greatest in terms of division

Just not what you usually mean by greatest

Yeah! You can define a new order instead based on division, and that always works

But it’s no longer the usual sense of size

For example in Z, there is no way to compare two primes anymore

I have no idea how this conversation statred

Oh, that

Okay time to get a bit more technical

In math, we have a bunch of different “types” of size

In N, the absolute value function is fucking awesome, because it:

• respects addition
• respects multiplication
• is injective

It’s still true for Z, but you lose injectivity

It’s d and -d as i said

Hmmm sure, but any other example is automatically going to be a lot more complicated, I’m warning you

5 is prime in Z, but it is no longer prime in Z[i]. Indeed you can see that (2+i)(2-i) = 5, but 5 does not divide either of them

So gcd(5, 6+3i) = 2+i or 2-i, and there isn’t a meaningful way to distinguish between the two that isn’t arbitrary

[rugged locust]

Lmao just realised my example doesn’t work, I’ll come back to this in a few hours and I’ll try to come up with something (with some kind of cyclotomic ring or quadratic extension of Z probably)

If you want a really simple and boring placeholder example, gcd(2,3) = 1, i, -1 or -i

[charred roost]

Here's another example, but not exactly numbers: consider x(x-1) and x(x-2) as polynomials over R. They have infinitely many GCDs: cx for any c in R is a GCD of x(x-1) and x(x-2). However, if you consider them as polynomials over Z, their only GCDs are x and -x

[lavish river]

@rugged pasture for your problem, maybe you can actually use the facts from my problem?? we show that a | b iff ord_p(a) <= ord_p(b) for all primes p

and we have in part (d) (the one you saw) an equality for gcd(a,b). my professor offered this as an alternate approach to Bezout's relation in general

[hoary shell]

If n and m are odd and not divisible by 3 then 24|n^2-m^2. How do you prove that?

The part where it says not divisible by 3 bugs me

[rugged locust]

||take the equation mod 8 and mod 3||

[hoary shell]

Wouldn't proving it modulo 3 show it is divisible by 3?

[rugged locust]

proving that it's congurent to 0 mod 3, yes

[hoary shell]

Wouldn't mod 8 be more annoying with all these combinations

that's like 4 permutations for the tuple (m,n)

If my combo is not wrong

(1,1),(1,5),(1,7)
(5,1),...

For the tuple

if n is odd then n^2 is even

so n=0 mod 2

my question was is there anything other than just make a dry table and compute

I can list quadratic residues mod 8 and 3

[rugged locust]

nope

lol

it's a boring question, from that perspective

[hoary shell]

Did I actually say that

What doing elementary number theory midnight does to a mf

Thanks btw i was just being braindead

[fickle tree]

guys im kinda confused bc my textbook does not explain it at all
if you have 3x = 3 (mod 6), you can just divide everything, x = 1 (mod 2)
||gcd(3,6) = 3||
then, why when solving 3x = pi (mod 2pi) you can simplify it to x = pi/3 (mod 2pi/3)
||gcd(3,2pi) = 1||

i think im missing smth

[rugged locust]

I would caution against this method of “dividing” out numbers in a congruence equation

It sounds like it can go wrong very easily if you don’t know what you’re doing

[fickle tree]

thats why im asking lmao

[rugged locust]

So, here’s how I would do it:
3x = 3 (mod 6)
3(x-1) = 0 (mod 6)
And so what that means is that x-1 is equal to 2 OR 6

The big, big, big big big problem in modulo arithmetic is that you get the existence of zero divisors, i.e. numbers a and b, that are both not equal to 0, such that a*b is equal to 0

So whenever you do division in module arithmetic you need to be very, very careful

And, in fact, avoid doing it as much as possible

[fickle tree]

so how would you solve the other one
3x = pi (mod 2pi)

[rugged locust]

Unless one side is 0, in which case you can carefully look at what two numbers can multiply to 0

[rugged locust]

For the second question, there is actually a problem with one of your points

The gcd() function makes sense as long as you’re working with integers. So the congruence equation 3x=3 (mod 6) is explicitly dealing in terms of integers only, and everything is fine

But then in your second equation, we are now taking mid 2π, which is no longer an integer.

So in fact, gcd(3, 2π) = 3

Because 2π * 3/2π = 3, so 3 does divide 2π in the real numbers

[fickle tree]

i see where you are going

alright this makes more sense now

[rugged locust]

So, what that means is, when you take modulo by a non-integer (in fact non rational) x, everything can now multiply to zero

Because for all real numbers y, y*y/x = x = 0 (mod x)

[fickle tree]

can we say gcd behaves somewhat like min

[rugged locust]

In the real numbers yes

[fickle tree]

thats what i was missing then yeah

tysm
you made it super clear

[rugged locust]

So, really the “correct” way to understand what (mod 2π) actually means, is that it is the quotient ring R/2πZ (actually not sure that this 100% works but I’m tired)

[rugged locust]

But that requires you to understand abstract algebra, which is a bit too much

[fickle tree]

ig you could also just write 3x = pi (mod 2pi) as
3x = 2kpi + pi, so
x = 2kpi/3 + pi/3

[rugged locust]

When you see mod 2π, you can just think of it as the sine function

That’s the simplest way to think about it

i.e. 3x = π (mod 2π) becomes sin(3x) = sin(π)

And now you can sidestep all the worrying algebraic issues

[fickle tree]

thats clever

alright again, tysm