Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
3
votes
2answers
32 views
Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$ [duplicate]
Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$, given that $l, m \in \Bbb{N}$. I had this question on my number theory final that I took earlier today. This was the second part of a 2 part ...
1
vote
2answers
43 views
Prove if $(l,m)=1$ and $l\mid mn$, then $l\mid n$.
I just took my number theory final and this was on the exam as the second question. It said to use the canonical decomposition of $l, m$ and $n$ for the proof. This is what I put down on the exam:
...
3
votes
3answers
86 views
How to factor 5671?
The other day I wanted to factor 5671 in my head. (It turns out to be $53\cdot107$, but I did not know this at the time.) I quickly ruled out the easy divisors, 2, 3, 5, 7, 11, and 13. At this point ...
1
vote
3answers
35 views
Primitive Roots
Given $p$, $q$ both primes such that $q = 2p + 1$, I need to prove that $-4$ is a primitive root mod $q$.
So far haven't found a direction that could lead me to the solution.
Any suggestion or short ...
1
vote
2answers
35 views
A new prime divides $a^p+1$
Let $a\in \mathbb{Z}$ and $p, q\in\mathbb{P}$. If $q\mid a+1$, there exists at least a prime $r \neq q$ such that $r\mid a^p+1$ (except for some trivial cases).
1
vote
3answers
86 views
If a relation is reflexive is it symmetric and transitive?
If a relation is reflexive is it symmetric and transitive ?
let ~ means " in relation with "
if A is a set , ~ is a relation on $A$, prove that:
if $a$~$a$ for any $a$ $\in$ A then
1- $x$~$y$ ...
1
vote
1answer
29 views
Why is $\sum_{d \mid N} N/d ϕ(N/d) ϕ(d) = N^2 \prod_{p \mid N} (1 - 1/p^2)$?
In the end, given the Euler totient function $ϕ$, I want to understand why:
$$ \sum_{d \mid N} (N/d) ϕ(N/d) ϕ(d) = N^2 \prod_{p \mid N} (1 - 1/p^2)$$
Do you have any hints regarding this?
...
2
votes
2answers
46 views
$\frac{1}{ab}=\frac{s}{a}+\frac{r}{b} \overset{?}{\iff}\gcd(a,b)=1$
$$\frac{1}{ab}=\frac{s}{a}+\frac{r}{b} \overset{?}{\iff} \gcd(a,b)=1$$
This seems almost painfully obvious because it is just $ar+bs=1$ in another form. This second form is the definition of ...
1
vote
1answer
22 views
finding a primitive root.
It says for part A to Find a primitive root r of 38? Im not sure if I did it right.
I first calculated $\phi(38)=\phi(19*2)=18$. So there are 18 numbers that are relatively prime to 38. Listing them ...
1
vote
1answer
35 views
$a \mid bc \overset{?}{\implies} \frac{a}{(a,b)} \mid c$
If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
0
votes
5answers
61 views
$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$
In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
2
votes
1answer
46 views
Solving the equation for $x$ in $Z_n$
How do you solve for x in the the $Z_n$ specified? For example, for the equation:
1) $3\odot x\oplus8\equiv1(\rm{mod} 10)$ or
2) $342\odot x\oplus 448\equiv73(\rm{mod}1003)$
How would you solve for ...
4
votes
1answer
62 views
(USAJMO)Find the integer solutions:$ab^5+3=x^3,a^5b+3=y^3$
Find the integer solutions:
$$a·b^5+3=x^3,a^5·b+3=y^3$$
This is the first problem of today's USAJMO (has finished),I only find a trival result that $x\equiv y \pmod6$ and $abxy≠0 \pmod 3$.
Thanks in ...
3
votes
6answers
79 views
$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$
Problem
So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$.
Attempt
This is a useful proposition given by the book:
Proposition 12. $11$ divides a ...
3
votes
3answers
100 views
How to show that $a$ can be divided by $6$ if and only if it can be divided by both $2$ and $3$?
Prove that for: $a \in\mathbb Z$, $a$ is divisible by 2 and $a$ is divisible by 3 if and only if $a$ is divisible by 6.
EDIT: Sorry, I wasn't aware of how exactly this site worked. This is pretty ...
