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

learn more… | top users | synonyms (1)

8
votes
2answers
480 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
60 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
0
votes
0answers
57 views

Solving system of inequalities, with solution in only natural numbers, with priority on variables

If I have the equations $27a+30b+33c+36c \geq x$ $a+b+c+d=4$ and want to solve them using only natural numbers (including 0) for both $x=131 $ and $x=142 $ preferably but not necessarily with $...
11
votes
4answers
197 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
69 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 ...
3
votes
5answers
224 views

Prove that $\sqrt{n^2 + 2}$ is irrational

Suppose $n$ is a natural number. Prove that $\sqrt{n^2 + 2}$ is irrational. From looking at the expression, it seems quite obvious to me that $\sqrt{n^2 + 2}$ will be irrational, since $n^2$ will be ...
6
votes
1answer
65 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 ...
0
votes
1answer
348 views

Show natural numbers ordered by divisibility is a distributive lattice.

I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR. I know it can be shown that a AND (b OR c) >= (a ...
0
votes
4answers
60 views

Is there a quick parity test for integers expressed with odd radicies?

For integers expressed with an odd base, is there an easy way to tell if the number is odd or even? For an even base, if the ones digit is even, so is the integer. But this doesn't hold true for odd ...
2
votes
2answers
60 views

Alternate way to Prove or disprove $6\mid n(n+1)(n+2)$

This is my proof, I'm wondering if I'm correct, and how to do without induction. My Work Basis Step $$\frac{(1)(2)(3)}{6} = 1$$ Inductive Hypothesis Assume that $\dfrac{k(k+1)(k+2)}{6} = d$ where ...
3
votes
2answers
109 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
136 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 ...
1
vote
1answer
70 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) =(y, p) = 1$. For what $p$ does their exist $x$ and $y$ such ...
3
votes
1answer
49 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
139 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
65 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: $x^2+y^2=5\...
0
votes
2answers
56 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
47 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
53 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 ...
2
votes
1answer
66 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 \mathbb{Z}$...
2
votes
1answer
49 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 13|...
1
vote
4answers
65 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 the ...
2
votes
3answers
71 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 = 7+...
3
votes
7answers
197 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
287 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?
0
votes
0answers
38 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$, $\overline{196}$ ...
2
votes
2answers
226 views

If $a > b+1$ then there is $M > 1$ so that $a^n - b^n$ is divisible by $M$ for all positive integers $n$. Prove by induction that $M = a - b$.

The problem: It turns out that if $a$ and $b$ are positive integers with $a > b + 1$, then there is a positive integer $M > 1$ such that a $a^n − b^n$ is divisible by $M$ for all positive ...
0
votes
3answers
70 views

The equation $x^2+3y^2=m$ has no solutions when $m\equiv 2\bmod 4$

For every integer $m$ such that $2$ divides $m$, and $4$ doesn't divide $m$, there are no integers, $x$ and $y$ that satisfy $x^2 + 3y^2 = m$. Use a contradiction (assume the negation is true) Is ...
3
votes
1answer
67 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
197 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
41 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 p_{...
2
votes
1answer
49 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 ...
4
votes
1answer
324 views

Goldbach's conjecture can't be proved to be undecidable?

Conjectures concerning natural numbers which could be settled by a counterexample can, as far as I understand, not be proved to be undecidable without being proved not having a counterexample at the ...
12
votes
3answers
2k 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 ...
2
votes
1answer
179 views

Question on congruence

Prove if $n|m$ where $n$ and $m$ are integers greater than $1$ and $a ≡ b ($ mod $ m)$ then $a ≡ b($ mod $n)$
2
votes
0answers
50 views

prove two sets have the same g.c.d.

$a_n,b_n$ are two sequence valued in $[0,1]$ and $a_0=1,b_0=0 $. the following equation holds: $$a_n=\sum_{k=1}^{n}b_ka_{n-k}\tag{1}$$ $$A=\{n:a_n>0\}-\{0\}$$$$B=\{n:b_n>0\}$$ further more,...
7
votes
4answers
351 views

Binary operation commutative, associative, and distributive over multiplication

Is there any binary operation that is commutative, associative, and distributive over multiplication? I asked this question in my head a while ago, and I posted it in various forums. However, having ...
2
votes
2answers
34 views

If $2a^2 = b^2$ then $2$ is a common divisor of $a$ and $b$?

The question is: Prove the statement or disprove it using a counterexample. If $2a^2 = b^2$, where $a,b\in \mathbb Z$, then $2$ is a common divisor of $a$ and $b$? The only thing that works ...
1
vote
2answers
145 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and $4a^...
3
votes
1answer
39 views

Prove that $\gcd(6n-1, 2n-4) = 1$ or $11$

Question: Prove that if $n$ is an integer, then $\gcd(6n-1, 2n-4) = 1$ or $11$. Would I have to use the Euclidean algorithm to solve this problem? How would I go about finding values of $n$ ...
0
votes
1answer
62 views

showing the natural numbers exist from axioms (help with making sense of book)

I'm now on page 40 of a set theory book and I've hit the natural numbers. I think the book has oversimplified some things. The successor of a set $x$ is defined to be $S(x)=x\cup\{x\}$ A set $I$ is ...
1
vote
1answer
84 views

Name of Legendre symbol?

This may seem stupid question, but I'm curious about this. Generally, $(a/p)$ is called "the Legendre symbol" where $p$ is an odd prime, but I don't like this naming since this naming is not formal. ...
1
vote
0answers
60 views

Proving Euler’s congruence and Legendre

So the question is "Prove Euler's congruence $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \bmod p$ for odd primes $p$ and $a$ in $\mathbb{Z}$." So I know that $$\left(\frac{a}{p}\right) = \...
1
vote
1answer
26 views

Using Euler theorem show that $a^{\frac{\varphi(m)}{2}}\equiv \pm1 \pmod m,~where~(a,m)=1$.

Euler Theorem: $a^{\varphi(m)}\equiv 1 \pmod m ,$ For $(a,m)=1.$ Using the above show that for $m=p^\alpha$ where $p$ is prime and $m\geq3$ $$a^{\frac{\varphi(m)}{2}}\equiv \pm1 \pmod m,~where~(a,m)...
1
vote
1answer
58 views

Fermat's $p=a^2+b^2$ theorem

There is one little part of the proof I didn't quite get. If we assume that $p$ is a prime such that $p \equiv 1\pmod 4$ and $x$ an element of order $2$ in $\mathbb{Z}_p$. Why $x$ must be equal ...
0
votes
1answer
147 views

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$.

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$ where a and b are positive integers. T(a) represents the number of divisors number a has. Source: 3rd ...
11
votes
2answers
194 views

How can I prove analytically the number $2^{100000}+1$ is not prime??

How can I prove analytically the number $$(2^{100000}+1)$$ is not prime??
0
votes
0answers
76 views

Can we use the distance to nearest prime to approximate large integers?

Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows: Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x. ...
1
vote
2answers
45 views

Prove that $\{2k+5 \mid k\in \mathbb{Z}\} = \{2k+3 \mid k\in \mathbb{Z}\}$.

Prove that $\{2k+5 \mid k\in \mathbb{Z}\} = \{2k+3 \mid k\in \mathbb{Z}\}$. I know how to do $\{2k+5 | k\in \mathbb{Z}\} \subset \{2k+3 \mid k\in \mathbb{Z}\}$. What I'm having trouble doing is ...