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

learn more… | top users | synonyms

1
vote
3answers
55 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
166 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
393 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
26 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
34 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
13 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
29 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
71 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 ...
1
vote
1answer
26 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 geometric way, like this one: However, I couldn't find any that involves 3D geometry. I also couldn't ...
1
vote
0answers
52 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
49 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
75 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
70 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
54 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
40 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
58 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
56 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
38 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
125 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
36 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 ...
-2
votes
1answer
21 views

Comparing coeficients of modulo arithmetic simultaneous equations [closed]

Consider set of simultaneous modulo equation, $n> 2$ being prime and $xy \ne 0 \mod n$. $2x +2y=e \mod n$ $ax+by=e \mod n$ How do i show that a=2 and b=2 (mod n for both). is it just clear?
8
votes
1answer
196 views
+50

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 ...
3
votes
0answers
83 views
+50

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
36 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
76 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: ...
0
votes
0answers
28 views

Prove Infinite Primes from Fermat Numbers [closed]

Assume that Fermat numbers $F_m$ are pairwise relatively prime. Prove, given this, that there are infinitely many primes.
-1
votes
0answers
109 views

attempt Legendre conjecture [duplicate]

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: ...
0
votes
1answer
58 views

The definition of “Dhuruva Numbers” [closed]

From my readings I encountered this number called "Dhuruva Numbers" Dhuruva Numbers are defined as follows: Definition. The numbers which do not change when performing a single operation or a ...
2
votes
2answers
53 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
75 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
77 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
31 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 ...
-2
votes
0answers
33 views

Number theory: gcd(a,b)= gcd(a+b, lcm(a,b)) ???? [closed]

Prove for any integers a, b : gcd (a,b)= gcd (a+b, lcm(a,b)) Thanks a lot....any hints would be apreciated
0
votes
0answers
48 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
35 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? $$
8
votes
3answers
142 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 ...
1
vote
3answers
50 views

If gcd$(a, 4) = 2$ and gcd$(b, 4) =2$, then gcd$(a + b, 4) = 4$ [closed]

If gcd$(a, 4) = 2$ and gcd$(b, 4) =2$, then gcd$(a + b, 4) = 4$ can someone help me solve this.
0
votes
2answers
62 views

How do I generate group table for elliptic curves over finite fields

Can someone please explain how to generate a group table for an elliptic curve over a finite field? The number of solutions or points are about 16 and it is not possible to do them by adding each ...
2
votes
2answers
67 views

Determining $\gcd(94, 27)$

I want to determine $\gcd(94, 27)$. Using the Euclidean algorithm, I got \begin{align} 94 &= 27 (3) + 13 \\ \implies 27 &= 13 (2) + 1 \\ \implies \;\;2 &= 2 (1) \end{align} Does this ...
0
votes
1answer
37 views

Solving $y^2 = 1263465 + 144x$ for integers $x,y$

I've thrown this equation up as part of some research I'm doing. $$y^2 = 1263465 + 144x$$ I was hoping there is a quick way to solve this without stepping through all the values. The value I'm ...
2
votes
4answers
34 views

Finding solutions to $h(j)=15+j^2 \mod 17, j \in \mathbb{N}$

I have a function such as this: $$h(j)=15+j^2 \mod 17, j \in \mathbb{N}$$ When $h(j)=7$ I know that there is a solution to this as: $h(3)=15+(3)^2 \mod{17}=7$ How can I prove that there no solutions ...
0
votes
0answers
29 views

Group tables for elliptic curves over primes

When constructing a group table for an elliptic curve modulo a relatively large prime $p$, say 23, are adding a few points with respect to each other enough to establish symmetry and thereby deduce ...
-2
votes
0answers
32 views

Maxima and minima of 2 variable function with conditions

Let $a=2001$. Consider the set $A$ of all pairs of integers $(m,n)$ with $n\not=0$ such that $m<2a$ $2n\mid 2am-m^2+n^2$ $n^2-m^2+2mn\le 2a(n-m)$ For $(m,n)\in A$, let $$f(m,n)=\frac ...
1
vote
2answers
56 views

$x!=y^n$ for $x,y \neq 0,1$

A straightforward problem (find all integers such that $m!+3=n^2$) led me into thinking about the integers for which: $$x!=y^2$$ is true. I argued that other than the trivial case ($x!=1$) that this ...
-1
votes
4answers
109 views

Is zero an even number? [duplicate]

A quick google returns the answer on the parity of zero: Zero is an even number. In other words, its parity—the quality of an integer being even or odd—is even. The simplest way to prove that zero is ...
1
vote
0answers
25 views

Definition of infimum and supremum in being greater than elements

Suppose you have a set, $\mathbb{N}$, the set of natural numbers.The proof by contradiction is simply that you assume. $a = \sup \mathbb{N}$ The definition of $\sup = a$ would then be that. $a = ...
0
votes
1answer
23 views

Problem regarding Gauss's Lemma

In Gauss'Lemma is it necessary for $a$ in $\left(\frac{a}{p}\right)$ to be a prime? I've checked a couple of books but there seems to be no restriction of this kind on $a$ just that $a$ and $p$ should ...
3
votes
2answers
55 views

Solve $2^x\equiv 5\pmod{13}$

I know the solution is $x\equiv 9 \pmod{12}$. I worked it by doing the donkey work of taking powers of $2$ : $2^2, 2^2, 2^3, \ldots, 2^{12}$ and picking the one that reduces to $5$. Just wondering if ...
6
votes
3answers
108 views

Elementary proofs of prime gap theorems?

"Obviously" it is thrue that $p_{n+1}<2p_n$. Testing for $n<10$ shows it is true for small $n$ and no mathematician or wannabe has ever doubt that it is true for big $n$. But there is no real ...
0
votes
2answers
49 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...