Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

1
vote
1answer
38 views

Greatest common divisor is divisible by every common divisor [duplicate]

Can anyone give a proof for the following elementary assertion without use of Bézout's theorem which says that The Greatest Common Divisor of two integers is an integer linear combination of them. ...
1
vote
2answers
40 views

How does this proof that the square of an integer, not divisible by 5, leaves a remainder of 1 or 4 when divided by 5 work?

Below I have a part of a proof of the fact that the square of an integer, not divisible by $5$, leaves a remainder of $1$ or $4$ when divided by $5$. But I am wondering where does the part highlighted ...
0
votes
2answers
41 views

How do I prove that $x^s=(-1)^k \sum_{k=0}^{(r-1)/2}\binom{r}{2k}p^{s(r-2k)}$ has no solutions?

I have been struggling to prove that the following diophantine equation has no integral solutions if $r$ is odd, $s,p>1$ $$x^s=(-1)^k \sum_{k=0}^{(r-1)/2}\binom{r}{2k}p^{s(r-2k)}$$ Any hint on how ...
13
votes
2answers
651 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
3
votes
1answer
46 views

How many co-prime pairs are there between 1 and N?

I suspect it's $$n^2 - \sum_{i=1}^n \phi(i) + 1$$ with $\phi(i)$ being the Euler function for the number of co-primes to $i$ between $1$ and $i$. But I have absolutely no proof to this but for example ...
2
votes
1answer
58 views

Show that there are at least $2$ elements in $U(n)$ such that $x^2=1$.

I am working on some exercises in Joseph Gallian's Contemporary Abstract Algebra. I came upon the following: Show that there are at least $2$ elements in $U(n)$ such that $x^2=1$, for $n>2$ ...
2
votes
1answer
24 views

Solve the congruence $x^2=x \mod (2 \cdot 3)^2. $

How to solve the congruence $x^2=x \mod (2 \cdot 3)^2? $ Using brute forse it is easy to show that $x=0,1,9,28.$ But how to get the result by calculation?
1
vote
0answers
25 views

Unique Solution To The Diophantine Equation

Show that the following Diophantine equation has a unique solution in positive integers $x^n+y^n=(x+y)^m$ with $x>y, m>1,n>1$. This could be solved by a direct use of Zsigmondy's theorem. ...
0
votes
0answers
29 views

How to prove a congruent to b (mod n) is a bijection?

I can prove it's an equivalence relation, but NO idea how to prove it's a bijection. I know I need to prove it's surjective/injective, but how do I establish it to even be a function?
0
votes
0answers
23 views

Is subtraction a binary operation on $S$

According to what I have been instructed before seeing this question, am suppose to subtract these number until I obtain a set of numbers that are non-negative and all less than 6.I am trying to ...
1
vote
0answers
26 views

Show Equivalence of Binary Quadratic Forms

I've been stuck on these two problems from my problem set for quite a while. Any help would be appreciated! 2)Suppose that $ax^2 + bxy + xy^2$ is equivalent to $Ax^2 + Bxy + Cy^2$. Show that $gcd ...
-2
votes
10answers
148 views

Show that the number $n$ is divisible by $7$ [duplicate]

How can I prove that $n = 8709120$ divisible by $7$? I have tried a couple methods, but I can't show that. Can somebody please help me?
0
votes
2answers
45 views

a question about relatively prime numbers

Is it true that if $m, n$ are relatively prime integers, then $mn$, $m-n$ are also relatively prime? It seems intuitively true but I can't prove it... Could anyone help me how to prove it?
4
votes
2answers
57 views

Find minimum of $a+b$ if $13|a+11b $ and $11|a+13b$

Find minimum of $a+b$ if $13|a+11b $ and $11|a+13b$ where $a,b>0$. My attempt : $13|a+11b \implies 13|a+24b$ . Similarly we get $11|a+24b$. Now $\gcd(11,13)=1$, so, $143|a+24b$. Therefore $a+24b ...
6
votes
1answer
122 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
3
votes
0answers
39 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
3
votes
4answers
51 views

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$. Hello. I am working on a review sheet for my test tomorrow and I am stuck on this ...
10
votes
7answers
924 views

Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$. I am rather confused by this question. This is my attempt so far: For $n = 2$ $2^5 ...
2
votes
2answers
36 views

Show that $ p^{(q-1)} + q^{(p-1)}$ is congruent to $1 \hspace{1mm } ($mod $ pq)$

Same review sheet, sorry for posting so much. But any help is appreciated. Let $p$ and $q$ be distinct prime numbers. Show that $p^{(q-1)} + q^{(p-1)} \equiv 1 \hspace{1mm } ($mod $pq)$. (hint: ...
2
votes
1answer
57 views

Number of solutions of $3x^2 - 5x + 3\equiv 0 \pmod{m}$?

I'm asked, for each of the following values of $m$, to find the number of solutions (in the set $Z_m$) of the quadratic congruence $3x^2 - 5x + 3\equiv 0 \pmod{m}$. For $m=53$ $m=73$ ...
8
votes
2answers
418 views

Let $a=43120$ How many positive divisors does a have?

I am doing a review assignment and I'm stuck on this problem. a) How many positive divisors does $a$ have? I got $60$ b) How many positive integers less than $a$ are relatively prime to $a$? I got ...
1
vote
1answer
53 views

Find the residue of $1!+2!+…+n! \pmod{m}$ for $m>n$

Find the residue of $ 1!+2!+........+n! \pmod{m}$ for $m>n$ $n,m$ are positive numbers and need not be primes. is there any known proof or result for this thanks
13
votes
4answers
170 views

Proving $1+2^n+3^n+4^n$ is divisible by $10$

How can I prove $$1+2^n+3^n+4^n$$ is divisible by $10$ if $$n\neq 0,4,8,12,16.....$$
0
votes
2answers
47 views

What does the “or” symbol mean as in “$ d\mid a$”

What does the "or" symbol mean as in the following post: How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$? In particular, the symbol is used in the above linked post in the following ...
6
votes
1answer
58 views

Divisibility of numbers between $n^3$ and $n^3+n$

Let $n$ be a positive integer. Given are numbers $n^3,n^3+1,\ldots,n^3+n$. Of them, $a$ are colored red, and $b$ others blue. The sum of the red numbers divides the sum of the blue numbers. Prove that ...
2
votes
2answers
21 views

Proving an identity of the Möbius function and Euler’s totient function product

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
5
votes
3answers
78 views

Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$

Prove that, the difference between the product of the first 2000 even numbers and the first $2000$ odd numbers , is a multiple of $2001$. Please show the method. I have started with the following ...
0
votes
1answer
26 views

Application of the Jacobian

I have been stuck on this question for a while now to no success. Help would be appreciated. Consider x and y such that (x, p) and (y, p) = 1. For what p does their exist x and y such that $x^2 + ...
4
votes
1answer
42 views

Modulo Arithmetic of Complex Numbers

Suppose $a,b,c \in \mathbb{C}$ such that $$a+b+c\in \mathbb{Z},$$ $$a^2+b^2+c^2=-3,$$ $$a^3+b^3+c^3=-46,$$ $$a^4+b^4+c^4=-123$$ then find $(a^{10}+b^{10}+c^{10})\pmod{1000}$. I only observed that ...
1
vote
1answer
26 views

Existence of a generator over multiplication for integers modulo p

If we consider the integers modulo a prime $p$, then for every $x \not \equiv 0$ (mod $p$), we can get any $b \not \equiv 0$ by adding $x$ a number of times to itself. Is the same true for ...
2
votes
3answers
59 views

Sum of squares and $5\cdot2^n$

Does anyone know of a proof of the result that $5\cdot2^n$ where $n$ is a nonnegative integer is always the sum of two squares? That is, nonzero integers $x,y$ must always exist where: ...
0
votes
2answers
39 views

Properties of addition and multiplication modulo $m$

I was studying some number theory and I came across this theorem in a book, but unfortunately there was no proof of it. Can somebody tell me the proof? $$(a + b) \bmod m = ( (a \bmod m) + (b \bmod m) ...
1
vote
0answers
15 views

Bertrand's postulate for primes congruent to 1 modulo 4

One should be able to show that there is a prime congruent to 1 modulo 4 between n and 2n for every sufficiently large n. Does anyone know a reference for this with an explicit bound on how large n ...
0
votes
3answers
31 views

Chinese Remainder Theorem Finding the Modulo

Find numbers $t,u,v$ so that $33t+2 = 20u+13 = 29v-1 $ This is a Chinese Remainder Theory problem, but the problem I am having is finding what are the appropriate modulo. I figure it is easiest to ...
1
vote
2answers
77 views

Fermat's theorem, sum of prime squares.

By Fermat's theorem, a prime $p$, is a sum of two squares if and only if $p \equiv 1 \pmod 4$. I am wondering if there is any extension of this theorem or result that will give me the primes of the ...
0
votes
2answers
24 views

How to prove $x^2=-1$ has a solution in $\mathbb{Q}_p$ iff $p=1\mod 4$

Let $p$ be prime and let $\mathbb{Q}_p$ denote the field of $p$-adic numbers. Is there an elementary way to prove $x^2=-1$ has a solution in $\mathbb{Q}_p$ iff $p=1\mod 4$? I need this result, but I ...
2
votes
1answer
52 views

Group-like structures over the integers and functions on them

The integers with addition build a group $\langle \mathbb{Z},+,0\rangle$. The functions $\operatorname{succ}:\mathbb{Z} \rightarrow \mathbb{Z}$, $\operatorname{pred}:\mathbb{Z} \rightarrow ...
2
votes
1answer
45 views

Prove that $13 | (a^2 + b^3) \Rightarrow 13|b$

I have to prove that $13|(a^2+b^3)\Rightarrow 13|b$. I know that: $13|a \land 13|b \Rightarrow 13|(a+b), $ $13|a \Rightarrow 13| a^2,$ $13|b \Rightarrow 13| b^3,$ $13|a \land 13|b \Rightarrow ...
1
vote
4answers
48 views

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9).

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9). I'm not too sure how to approach this. I first noted that $(6,9) = 3 \neq 1$ so I cannot use ...
2
votes
3answers
31 views

Solutions for a system of congruence equations

I have a system $$ \begin{cases} x \equiv 7 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ How can I show that the system does not have any solutions? I know that the first implies that $x = ...
3
votes
7answers
140 views

For what $n$ is $n! = 2^8\cdot3^4\cdot5^2\cdot7$?

How can one find $n$ when $n! = 2^8\cdot3^4\cdot5^2\cdot7$? And generally, How to solve this kind of questions? The textbook provided a poor answer.
1
vote
1answer
220 views

There does not exist a perfect square with all decimal digits 0 or 6 [closed]

How to show that there is no perfect square whose decimal representation consists entirely of digits 6 and 0?
4
votes
1answer
57 views

Show that $\limsup \pi(n)/n = 0$ with elementary techniques.

Suppose $S$ is a set $S \subseteq N$ and suppose $$\lim_{n \to \infty} \frac{|Z_n \cap S|}{n} = c \in (0,1).$$ How do we prove, using elementary means, that there is a composite number in $S$? If ...
0
votes
0answers
30 views

Why is $x^2=a \pmod{p_1p_2}$ solvable when $x^2=a \pmod {p_i}$ is solvable?

Burton - Number theory If $x^2=196 \pmod {23}$ and $x^2=196 \pmod{59}$ are solvable, then $x^2=196 \pmod{23\cdot 59}$ is solvable. Why? Here, since $\gcd(196,23\cdot 59)=1$, ...
3
votes
1answer
51 views

How find prime numbers $p_{i}$ such $p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$ is square number

Question: Let $n\ge 5$ be an odd number, show that: there exist (or does not exist) primes $p_{i}\:;\:i=1,2,\cdots,n$ such that $$p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$$ all ...
0
votes
2answers
62 views

Prove that $x=0.1234567891011\cdots$ is irrational [duplicate]

Prove that $x=0.1234567891011\cdots$ is irrational Proof: we argue by contradiction.suppose x is rational. then its decimal expansion ultimatetly periodic. Lets p denote the perid of this expansion. ...
2
votes
0answers
30 views

divisibility and k-power sum

Let $a_{1},\dots,a_{n},\,n>2$ distinct natural numbers. Prove that if $p_{1},\dots,p_{r}$ are prime numbers and they divide $a_{1}+\dots+a_{n}$ then exists an integer $k>1$ and a prime $p\neq ...
2
votes
1answer
36 views

If $p,q$ are prime numbers prove that $p=q^2+q+1$.

Prove that if $p$ and $q$ are prime numbers such that $p|q^3-1$ and $q|p-1$ then: a) $p|(q^2+q+1)$ b) $p=q^2+q+1$ It is easy to prove part a but I am having troubles with part b. Does anyone have ...
10
votes
3answers
1k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...