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

learn more… | top users | synonyms (1)

0
votes
2answers
152 views

Prove the following divisibility statements without use of induction

(a) $5$ $|$ $3^{3n+1}+2^{n+1}$ (b) $21$ $|$ $4^{n+1} + 5^{2n-1}$ (c) $24$ $|$ $2 \cdot7^n + 3 \cdot5^n - 5$ These are trivial by using induction. But I have tried to prove it by binomial theorem and ...
1
vote
1answer
422 views

Relatively prime numbers

Find the number of elements in the set $\{m:1\le m\le 1000,m$ and $1000$ are relatively prime$\}$. My attempt: We are to find the number of elements which have only $1$ as the common factor with ...
1
vote
1answer
95 views

When is $(a-1)(a-b)/b$ a positive integer?

Let $a,b \geq 1$ be positive integers and $S \subset \mathbb{N}^2$ where $$ S = \{(a,b)\in\mathbb{N}^2 : (a-1)(a-b)/b \text{ is a positive integer} \}. $$ How does one go about determining all the ...
1
vote
2answers
257 views

Representing an Integer as a Sum of at Most $k$ Triangular Numbers

What is the smallest $k$ such that every $n \in \mathbb{N}$ can be represented by a sum of exactly $k$ triangular numbers? For the sake of simplicity, I will assume $0$ is a triangular number. I've ...
2
votes
1answer
198 views

Difference sets avoiding quadratic residues

I have a homework question that is stumping me, and I am looking for an entry point. It goes like this: Suppose $p$ is prime. Prove that the largest set $S\subseteq\{0,1,\dots, p-1\}$ such that ...
0
votes
2answers
130 views

Show $[a]_m=[a]_n\cup[a+m]_n\cup\dots\cup[a+m(k-1)]_n$

Let $m$ and $n$ be positive integers such that $m|n$. Show that for any integer $a$ the congruence class $[a]_m$ is the union of congruences $[a]_n,[a+m]_n,[a+2m]_n,\dots,[a+n-m]_m$. Which is just ...
1
vote
0answers
35 views

How quickly can we find a modulated sequence of powers?

How quickly can we find an element of (at least) multiplicative order at least $p$, where $p \in \mathbb{N}$? The complete question is that we start with a number system of $s$ elements; for example ...
4
votes
4answers
635 views

Idea of the Proof : Existence of a & b so that (Any integer greater than 8) = 3a + 5b [duplicate]

Claim: Prove that for every integer $n \geq 8$, there exist nonnegative integers $a$ and $b$ such that $n = 3a + 5b.$ Proclaimed solution : Let $n ∈ \mathbb{Z}$ with $n ≥ 8.$ $\text{ Then } n ...
1
vote
1answer
78 views

Ambiguous definition of the set of Natural Number [duplicate]

According to the book "An introduction to the analysis of algorithms (written by Michael Soltys)", the author says in chapter 1 as follows. Let $\mathbb N = \{0, 1, 2,...\}$ be the set of natural ...
3
votes
2answers
120 views

Sum of two squares modulo a prime in $4\mathbb Z + 1$

I am trying to find the number of solution of the equation $$ x^2 + y^2 = 1 $$ in $\mathbb Z/p\mathbb Z$, where $p$ is a prime such that $p\in4\mathbb Z+1$. Apart from the trivial solutions $(0,\pm ...
5
votes
1answer
165 views

The number of solutions to $\frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N$

Denote $$g(n)=\{\{x,y,z\}\mid \frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N\},$$ $$h(n)=\{\{x,y,z\}\mid \frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,1\leq x\leq y\leq z,x,y,z\in\mathbb N\},$$ ...
2
votes
2answers
175 views

Show that this set of integers can be expressed in the form $7r+10s$ with $r, s$ non-negative integers.

The set of integers are: ${54,55,...,60}$ I am having trouble with the non-negative integers part, otherwise the question appears to be quite simple. I have that since $gcd(7,10) = 1$, by extended ...
2
votes
4answers
96 views

Proof that $3 \mid \left( a^2+b^2 \right)$ iff $3 \mid \gcd \left( a,b\right)$

After a lot of messing around today I curiously observed that $a^2+b^2$ is only divisible by 3 when both $a$ and $b$ contain factors of 3. I am trying to prove it without using modular arithmetic ...
1
vote
2answers
74 views

Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$

"Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$" I know that this has something to do with Euler's function, but i'm not sure how to apply it. A fellow on an IRC channel ...
6
votes
3answers
156 views

Solve $2^n=k^2+k+2$ for positive integers

This problem came from my own research ( research for fun, not professional ). I was able to simplify a little and solve some special cases, but I need a help to get the general case which is "Find ...
0
votes
1answer
54 views

Relation between $a$ and $a^{-1}$ in integer rings about evenness

Could I ask something seemingly simple? Well, let $N$ be a positive odd number (the reason why I set $N$ to be odd is I could actually solve the problem when $N$ is even which is easy) and $a$ is an ...
2
votes
2answers
230 views

$n$ is a natural number such that $n^5$ is odd

$n$ is a natural number such that $n^5$ is odd then which of the following is true? $1.n$ is odd $2.n^3$ is odd $3.n^4$ is even. $3$ is always true as any number multiplied by even times it will ...
10
votes
3answers
276 views

Math contest proof problem fractions

Could someone help me with this? Let $x, y, z$ be positive integers with greatest common divisor $1$. If $\frac 1 x +\frac 1 y=\frac 1 z$, then show that $\sqrt{x + y}$ is an integer.
3
votes
3answers
180 views

Probability for the sum of two random numbers being a prime number?

Suppose $N$ is a (large) fixed positive integer, and one is asked to randomly choose any two integers (numbers could be same as well) from $1$ to $N$ (including $1$ and $N$). Let the experiment be ...
1
vote
6answers
495 views

Prove that there are infinitely many natural numbers that can't be written as $a^2+p$

Generally speaking, if they ask us to prove that there are infinitely many numbers that can't be written in a certain way, how should we try to solve the problem? I've never seen a solution to such a ...
2
votes
0answers
90 views

show $\frac{n}{d}$ is the additive order

Prove that if $n>1$ and $a>0$ are integers and $d=gcd(a,n)$ then the additive order of $a\pmod{n}$ is $\frac{n}{d}$. *Additive order is the smallest positive integer that satisfies $ax\equiv ...
7
votes
2answers
305 views

Show that the sequence $1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,2,0,2,1,\cdots$ isn't periodic

Show that the sequence $\{a_n\}_{n\in \mathbb{N}} = \{x: x=$ the nth decimal digit of Champernowne's constant$\}$ is not periodic. For those who don't know what Champernowne's constant is, it's the ...
0
votes
1answer
105 views

A problem regarding the proof of ${p^nk\choose p^n}\equiv k\mod p$, where $p\nmid k$.

In this proof, there is a statement where: $$(a+b)^{p^nk}\equiv (a^{p^n}+b^{p^n})^k\mod p$$ I understand this part. But then it expands both sides binomially, and compares coefficients of ...
1
vote
2answers
86 views

'Coprime' problem related to integer rings

I am handling a problem involving the proof of whether two integers are coprime or not. Think of a positive integer $N$ and two integers $r$ and $s$ in $\mathbb{Z}_N$ such that $\gcd{(N, r)}=1$ and ...
2
votes
1answer
54 views

Calculating modular inverses with limited multiplication

Question Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications ...
1
vote
3answers
131 views

Prove that there are infinitely many perfect cubes of the form $p^2+3q^2$

Prove that there are infinitely many perfect cubes of the form $p^2+3q^2$ where $p$ and $q$ are integers. Hint: one approach is to set $p^2+3q^2=(a^2+3b^2)^3$ and then find $(p,q)$ in terms of $a,b$. ...
1
vote
1answer
119 views

Measuring the biggest difference in the reduced residue system modulo N

Is there a known means of measuring the biggest difference of consecutive elments of the reduced residue system modulo N? For example, say we have the reduced residue system modulo 15: [1, 2, 4, 7, ...
0
votes
3answers
653 views

Number Theory Congruent and Modulo problem

I have given a problem and I found out that I have a problem with explanation in words. I can solve it with numbers however when it comes to a problem where I have to explain in words, I don't know ...
16
votes
2answers
338 views

Question from Putnam '89: Primes of the form $101\ldots01$

I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input ...
3
votes
1answer
240 views

Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
0
votes
1answer
84 views

Find an integer $x$ such that $107 \equiv x \cdot 2005 \, \pmod{1302}$

If I write it out then $107 \equiv x \cdot 2005 \pmod {1302}$ means that $x\cdot2005 = q1302 + 107$, for some $q \in \mathbb{Z}$ (I could replace 2005 with 703 though that doesn't make it any ...
3
votes
2answers
144 views

Is every infinite set of natural numbers a sum of two infinite sets of natural numbers?

If $A,B\subseteq\{0,1,2,\ldots\},$ then $A+B=\{a+b:a\in A,b\in B\}.$ Is it true that for any $X\subseteq \{0,1,2,\ldots\}$ infinite, there exist infinite sets $A,B\subseteq\{0,1,2,\ldots\}$ such that ...
1
vote
1answer
72 views

On the rational Beatty sequence

Let $S(p/q, b) = \{[pn/q + b]|n\in\mathbb{Z}\}$, where $p, q$ are coprime positive integers and $b$ is any integer, be a rational Beatty sequence. I can't see why the following conclusion is true: ...
1
vote
1answer
79 views

What proportion of the natural numbers satisfy the following inequalities?

Let $\sigma_1(n)$ be the sum of the divisors of $n \in \mathbb{N}$, and let $$I(n) = \frac{\sigma_1(n)}{n}$$ be the abundancy index of $n$. What proportion of the natural numbers satisfy the ...
1
vote
5answers
298 views

If $x,y$ are integers such that $3x+7y$ is divisible by $11$, then which of the following is divisible by $11$?

I am currently studying for the GRE, and this question came up. Let $x$ and $y$ be positive integers such that $3x+7y$ is divisible by $11$. Which of the following must also be divisible by $11$? ...
0
votes
1answer
434 views

Prime Numbers And Perfect Squares

Find all primes $p$ and $q$ such that $p^2$+$7pq$+$q^2$ is a perfect square. One obvious solution is $p$=$q$ and under such a situation all primes p and q will satisfy. Further if $p\neq$$q$ then we ...
4
votes
0answers
125 views

Modified Pell equation: $x^2-D y^2 = m$, $m\neq1$.

How does one solve the Diophantine equation $$ x^2-Dy^2=m, $$ where $m$ is some fixed arbitrary integer? I understand that given the fundamental solution to $r^2-D s^2=1$, and any solution to the ...
4
votes
2answers
90 views

Is the assertion about the form $\alpha x+\beta xy+\gamma y$ true?

In my answer, I was led to conjecture the following: Statement: If $\gcd(\alpha,\beta,\gamma)=1,$ then every integer can be written as $\alpha x+\beta xy+\gamma y$ for integer $x$ and $y$. ...
2
votes
1answer
279 views

Find the number of sets $B$ such that $B \subset A$ , $|B|=m$, and the sum of the elements in $B$ is divisible by $p$.

Let $A=\{1,2,\ldots ,p\}$ where $p$ is a prime number. Find the number of sets $B$ such that $B \subset A$ , $|B|=m$, and the sum of the elements in $B$ is divisible by $p$.
2
votes
0answers
148 views

Wilson's theorem intuition

Wilson's Theorem: $p$ is prime $\iff$ $(p-1)!\equiv -1\mod p$ I can use Wilson's theorem in questions, and I can follow the proof whereby factors of $(p-1)!$ are paired up with their (mod $p$) ...
0
votes
2answers
71 views

The cubic function meets Number Theory

The cubic function$$ 2^{k + 1} x^3 + 3x^2 - d = 0 $$where $$ d,k \in {\Bbb Z} ,d \gg 2^{k + 1} $$ the discriminant $$ \Delta < 0 $$ so there is one real root and two imaginary roots. My ...
3
votes
2answers
178 views

Arithmetical functions summation

Problem (7.4.15) of Burton's Elementary Number Theory has been request that prove the following equalities. In this book isn't expressed Dirichlet multiplication and Riemann's zeta function before ...
3
votes
2answers
85 views

Let $a,k,m$ be integers. Prove that $\gcd(ka,km) = k\gcd(a,m)$.

Here is what I got so far: Let $\gcd(ka,km) = d$ Then by the Euclidean Algorithm, we have integers $s,t$ such that: $$s(ka) + t(km) = d \implies k|d $$ Let $$d/k = g = sa + tm. \tag{1}$$ So now ...
5
votes
3answers
446 views

Prime Number in triangle

I had a question here, the measures of the sides of a right triangle (a single unit) can be prime numbers? If they can not, why?! But, if you can, could you help me find an example?
1
vote
1answer
112 views

Last 3 digits of $2012^n$

Let $n\in\mathbb{N}$ such that the base $10$ expansion of $2012^n$ is $?\,?\,?\ldots ?\,4\,?\,4$ where $?$ is an unknown digit. Find all the possible values of the digit between the $4$s.
1
vote
0answers
100 views

A Gauss sum over a field.

Let $K$ be a field (not necessarily $\mathbb C$) and let $\zeta=\zeta_n$ be a primitive $n$th root of unity in $\bar K$. I would like to know if there is a formula calculating $$ \sum_{k=1}^n ...
3
votes
2answers
147 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
4
votes
2answers
146 views

If $x^2+ax+b=0$ has a rational root, show that the root is an integer. [duplicate]

So far I have Assume $a,b,x,y$ are integers; $\frac xy$ is rational; and that $\frac xy$ is in simplest form. WTS: $\frac xy$ is integer So $(\frac xy)^2 + a(\frac xy) + b = 0$; ${x^2\over y^2} = ...
2
votes
1answer
118 views

if $a/b+c/d=n$ then $|b|=|d|$

I have to prove that if gcd$(a,b)=1$ and gcd$(c,d)=1$ and if $a/b+c/d=n\in\mathbb{Z}$ then $|b|=|d|$. Here is my approach: $$a/b+c/d=\frac{ad+bc}{bd}=n$$ so $bd\mid (ad+bc)$. Also gcd$(a,b)=1$ and ...
-2
votes
3answers
499 views

Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.