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

learn more… | top users | synonyms (1)

6
votes
2answers
563 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
0
votes
0answers
27 views

Can a simple prime product be decoupled using only one variable using a computer algorithm?

Let $P(x) = D(x) + m(x)$ and $Q(x) = D(x) - m(x)$ where $D(x) = \sqrt{N} \cosh x$ $m(x) = \sqrt{N} \sinh x$ where $N = PQ =$ a prime product, and $P(x_0)$ and $Q(x_0)$ are prime number ...
2
votes
2answers
123 views

How do I solve this Olympiad question with floor functions?

Emmy is playing with a calculator. She enters an integer, and takes its square root. Then she repeats the process with the integer part of the answer. After the third repetition, the integer part ...
19
votes
4answers
400 views

At most one divisor in $[\sqrt{n},\sqrt{n}+\sqrt[4]{n}]$

In one math book I'm reading there was the following problem, given as an exercise: For any $n\in\Bbb N$ there is at most one divisor of $n$ in the interval $[\sqrt{n},\sqrt{n}+\sqrt[4]{n}]$. I ...
0
votes
0answers
32 views

Fermat Numbers are Prime Proof [duplicate]

Assume that the Fermat numbers $F_m$ are pairwise relatively prime. Prove from this that there are infinitely many primes. My proof can only involve that the Fermat numbers are pairwise relatively ...
2
votes
3answers
93 views

Prove that for any natural number $n$ there exists a prime number $p$ greater than $n$

Prove that for any natural number n there exists a natural prime number p , such that $ p>n $. How can I prove that ? Thank you.
1
vote
1answer
86 views

Four different positive integers a, b, c, and d are such that $a^2 + b^2 = c^2 + d^2$

Four different positive integers $a, b, c$, and $d$ are such that $a^2 + b^2 = c^2 + d^2$ What is the smallest possible value of $abcd$? I just need a few hints, nothing else. How should I begin? ...
11
votes
3answers
146 views

Prove that $a+b$ cant divide $a^a+b^b$ nor $a^b+b^a$

Let a and b be natural numbers so that $2a-1,2b-1$ and $a+b$ are prime numbers. Prove that $a+b$ cant divide $a^a+b^b$ nor $a^b+b^a$. I get that $gcd(a,b)=1$. I havent got anything special for now ...
4
votes
2answers
87 views

$A\subseteq \{1,2,3, \ldots 2000\}, $ and for any $a,b\in A,\; |a-b|$ is not equal to 4 or 7,

$A\subseteq \{1,2,3,\ldots2000\}$, and for any $a,b\in A,$ $|a-b|$ is not equal to 4 or 7. Then, at most, how many element does $A$ contain? For general condition,$|a-b|$ is not equal to $i$ or $j, ...
2
votes
3answers
203 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
0
votes
3answers
26 views

Solving for mod indirectly

How many positive integers $n$ exist such that $\frac{680}{n}$ is an integer? So, this is quite obvious, $680 \equiv 0 \pmod{n}$ How should I solve for $n$? There will be multiple $n$?
48
votes
10answers
6k views

Is there something special about 2015?

Is there some property which is satisfied only by the number 2015 (among natural numbers, say) or is there a relatively simple question for which the answer is, surprisingly, 2015? This is inspired ...
0
votes
1answer
71 views

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$)

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$) I'm having a trouble showing this. I think I need to ...
-1
votes
2answers
54 views

Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$)

Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$) This is a problem from Burton's Elementary Number Theory. The answer says $x \equiv 11+ t, y \equiv 5+6t$ (mod 13). I don't ...
1
vote
1answer
42 views

Proving $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$

Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$ My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then ...
2
votes
2answers
162 views

If GCD of a list of numbers is 1, is it a necessary condition that GCD of at least one pair of numbers from the list should be 1?

Suppose our numbers are {2, 6, 3}. GCD (2, 6, 3) = 1, GCD (2, 6) = 2, GCD (6, 3) = 3, but GCD(2, 3) = 1 If GCD(a,b,c) = p, GCD(a,b) = q, GCD(b,c) = r, GCD(c,a) = s, is it possible that p = 1 and (q ...
2
votes
2answers
48 views

Solve diophantine using modulus

Find all pairs of positive integers $(m, n)$ that satisfy, $mn + 3m - 8n = 59$ Using Modular arithmetic. Okay, this is a diophantine equation, where can I begin?
0
votes
1answer
70 views

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$. I cannot get heads nor tails of how to even start this let alone finish ...
1
vote
3answers
71 views

Infinitely many primes of the form $6n - 1$

Prove there are infinitely many primes of the form $6n - 1$ with the following: (i) Prove that the product of two numbers of the form $6n + 1$ is also of that form. That is, show that $(6j + 1)(6k + ...
4
votes
3answers
181 views

What is so great about 7?

I'm going to write down my problem verbatim: Write down the integers from $1$ to $50$ in rows of $10$ numbers each. Mark out $1$, and then cross out all multiples of $2$ greater than $2$ ...
4
votes
2answers
395 views

Where can the knight be?

The answer is 33. I get $24$. Because of $8 \cdot 3 = 24$? How can I do this using combinatorics?
0
votes
1answer
47 views

Use the least integer principle to prove the following.

Least integer principle: Every non-empty set of positive integers has a least element. Using this fact, define $r$ to be the least integer for which $j - qk > 0$ where $j, k \in \Bbb{Z}$ ...
0
votes
1answer
42 views

How many possible paths?

The answer is $32$. Its supposed to be $2^5$ but I do not see how you get that? The way I see it, there are $5$ ways to go up and $5$ ways to go right, total ways = $5x5= 25$
0
votes
0answers
24 views

Prove for each pair of integers $j, k : k > 0$, there exists a $q : j - qk > 0$

Prove for each pair of integers $j, k : k > 0$, there exists a $q : j - qk > 0$. I began by writing out all three cases, i.e. $C_1 \to j > k$, $C_2 \to j = k$, and $C_3 \to j < k$. ...
1
vote
1answer
36 views

Maximal Multiplication of All Possible Summands

I have recently got interested in the following problem: Give a decomposition of a natural number to natural summands whose multiplication is maximal. I have tried to solve this problem, and ...
1
vote
2answers
79 views

We write all the positive integers run together as follows: $123456789101112131415 . . .$

We write all the positive integers run together as follows: $123456789101112131415 . . .$ What three digit number begins at the $2014th$ digit? I was thinking number theory here. Modulus. Can ...
2
votes
1answer
74 views

Are there 3D geometric proofs of Fibonacci identities?

There is a significant number of identities involving Fibonacci numbers that can be proven in a sort of geometric way, as it is shown in the following picture: However, I couldn't find any such ...
1
vote
0answers
53 views

Evaluate $\sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$

Evaluate: $$I = \sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$$ $$I = \sqrt{2^{2006}\cdot (1 + 2^{5} + 2^{8} )} \pmod{17} = 2^{1003} \cdot \sqrt{2^8 + 2^5 + 1} \pmod{17}$$ The answer is $0$ ...
-1
votes
1answer
55 views

Solve $5991x + 289 \equiv 0 \pmod{2014}$

Solve: $$5991x + 289 \equiv 0 \pmod{2014}$$ $$5991x \equiv -289 \equiv 1725 \pmod{2014}$$ I need to find the inverse of $5991$ modulo $2014$. Start with Euclid's algorithm: $$5991 = 2(2014) + ...
3
votes
1answer
167 views

What is the inverse of the divisor sum function $\sigma $?

Let $(A, +, *)$ be the commutative ring of arithmetic functions with Dirichlet convolution as the multiplicative operation *. The element $$\sigma(n)=\prod_i \frac{p_i^{k_i+1}-1}{p_i-1}, \text { ...
2
votes
4answers
72 views

Proving that $x^5 = x \pmod{10}$ for every integer $x$. [duplicate]

Show that $x^5 = x \pmod{10}$ for every integer $x$. How can I approach this? Should I use induction? I am stuck trying to get it in terms of $x+1$. Some feedback would be appreciated.
4
votes
2answers
65 views

Prove that the sequence $p_i$ is bounded

Let $p_1,p_2,...$ be a sequence of natural numbers. $p_1$ and $p_2$ are prime and $p_n$ for $n\ge 3$ is the largest prime divisor of $p_{n-1}+p_{n-2}+2014$. Prove that $(p_n)$ is bounded.
0
votes
1answer
42 views

Let $m = \frac{(4^p - 1)}{3}$ Find the remainder when $2^{m - 1}$ is divided by $m$

Let $m = \frac{(4^p - 1)}{3}$ where $p$ is prime and $p > 3$. Show that the remainder when $2^{m - 1}$ is divided by $m$ is equal to $1$. I've tried various ways of setting $2^{m - 1} = km + 1$ ...
1
vote
3answers
78 views

How to find inverse Modulo?

Find the inverse modulo, Modulo inverse of $5991 \pmod{2014}$ ? I am aware of the Euclid algorithm, but I am not sure how to apply it here?
2
votes
3answers
67 views

Proof of non divisibililty of $\binom{n}{r}$ with a prime $p$

I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means ...
1
vote
1answer
40 views

A theory of radicals of integers?

It seems to me that radicals, natural numbers without power factors, generalize the concept of primes. You could ask after the nth radical and the number of radicals less than a specified number. But ...
4
votes
1answer
179 views

Question about Paul Erdős’ proof on the infinitude of primes

I was reading Julian Havil’s book Gamma where he talks about a short proof by Paul Erdős on the infinitude of primes. As I understand it, here are the steps: (1) Let $N$ be any positive integer and ...
1
vote
2answers
48 views

Pairs of integeres for which the arithmetic mean exceeds the geometric mean exactly by $2$

Suppose $0<x<y<2015$ are integers. How many pairs of $x$ and $y$ are there for which the arithmetic mean exceeds the geometric mean exactly by $2$? Progress Obtained the equation ...
12
votes
1answer
363 views

A set of integers whose elements all divide $2015^{200}$ but do not divide each other

Let $S$ be a set of natural numbers,such that each element divides $2015^{200}$ but for no two elements $a$ and $b$, $a|b$. Find the maximum number of elements in $S$ . $2015^{200}=(5\cdot ...
4
votes
1answer
224 views

Find all positive integers $n$ for some given condition.

Find all positive integers $n>1$ such that $n^2$ divides $2^n+1$ I found that $n$ is of the form $6k+3$.
1
vote
1answer
38 views

Prove that there no positive integral solution to this equation.

Prove that there doesn't exist positive integers $a,b,c,n$ such that this equality holds: $6(6a^2+3b^2+c^2)=5n^2$ I found reduced the equation as follows: $2a^2+b^2+3m^2=10r^2$ But any mod upto ...
1
vote
0answers
84 views

question about proof correctness of Legendre conjecture

I am trying to prove Legendre's conjecture in the following way: Between two consecutive squares there exist two primes. Zippy: 22-01-2015 Definition 1. We write $R(a)$ for the odd numbers in: ...
2
votes
3answers
91 views

Possible not countable extension of the natural numbers?

This question comes from:Is $1234567891011121314151617181920212223......$ an integer? We define $\mathcal{A}$ as the set of infinite strings of digits $$ \bar a_i=a_0 a_1a_2a_3\cdots a_i \cdots ...
2
votes
2answers
59 views

Find the least number b for divisibility

What is the smallest positive integer $b$ so that 2014 divides $5991b + 289$? I just need hints--I am thinking modular arithmetic? This question was supposed to be solvable in 10 minutes...
2
votes
1answer
82 views

How many ordered triples $(a, b, c)$ exist?

How many ordered triples $(a, b, c)$ of positive integers exist with the property that $abc = 500$? Breaking it up, $500 = 2^2\cdot5^3$ $abc = 2^2 \cdot 5^3 = 2\cdot 2 \cdot 5 \cdot 5 \cdot ...
5
votes
2answers
81 views

How to find all integer solutions of $p^2+q^2=((2q+1)^2+q+1)^2+1$

$$p^2+q^2=((2q+1)^2+q+1)^2+1$$ How do I find integer solutions to this equation? I've already found $(p,q)=(11,1)$. How do I go about finding new ones?
3
votes
1answer
39 views

If $ j , k , n$ are consecutive integers and $jn$ has last digit $9$, what is the last digit of $k$?

$ j , k , n$ are consecutive integers such that $0 < j < k < n$ and the units (ones) digit of the product $jn$ is $9$, what is the units digit of $k$? SAT Question. I don't know if we are to ...
0
votes
0answers
86 views

In terms of addition, multiplication, exponentiation, tetration, what would be the natural continuation here?

Consider the by addition recursively defined table: $$t(n,1)=1$$ If $n>=k$ $$t(n,k)=\sum _{i=1}^{k-1} t(n-i,k-1)-\sum _{i=1}^{k-1} t(n-i,k)$$ else $$t(n,k)=0$$ Then consider the similar but by ...
1
vote
1answer
42 views

Is there a set of integers where all differences are relatively prime?

Is there an infinite subset $\mathcal S\subset \mathbb Z$ with the property that for any 4-tuple of distinct elements $x,y,z,w\in \mathcal S$ $$ \gcd(x-y,z-w)=1? $$
6
votes
3answers
151 views

The maximum of $\binom{n}{x+1}-\binom{n}{x}$

The following question comes from an American Olympiad problem. The reason why I am posting it here is that, although it seems really easy, it allows for some different and really interesting ...