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

learn more… | top users | synonyms

0
votes
3answers
25 views

Solve diophantine equation using modular arithemtic

Solve for integers, $x, y$ $4258x+147y=369 \implies 4258x \equiv 369 \pmod{147}$ I got this question from SE, but I want to try this approach. I suppose we will find the inverse modulus of $4258 ...
1
vote
3answers
54 views

Last 2 digits of $2345^{369}$

http://i.stack.imgur.com/hte3J.jpg This webpage says last 2 digits of $2345^{369}$ is $75$. But considering only last 2 digits: $45^1 = 45$ $45^2 = 25$ $45^3 = 25$ The last 2 digits are always ...
1
vote
3answers
18 views

Can I conclude there's no $x/y$ such that $(x/y)^2=-1$ mod 3

Suppose $x^2+y^2=0$ mod 3. I want to show 3 divides $x$ and $y$. Assume $(y^2,3)=1$. Dividing $y^2$ gives $(x/y)^2=-1$ mod 3. Here I want to use the fact that $-1$ is not congruent to any square mod ...
0
votes
2answers
24 views

Show if $k$ is an integer, then $\sqrt[n]{k}$ is rational if and only if it is an integer.

$(i)$ Show that if the reduced fraction $a/b$ is a root of the equation $c_0x^n + c_1x^{n-1} + \cdots + c_n = 0, $ where $x \in \mathbb{R}$ and $c_0,\ldots,c_n \in \mathbb{Z}$ with $c_0 \ne 0$, ...
6
votes
3answers
187 views

Finding the number of divisors of a number?

How can I find the number of divisors of $2011\times2012\times2013\times2014+1$?
1
vote
0answers
33 views

Do you know any answer for equation y^2 = x^3 + k? [duplicate]

As you know, the equation y^2 = x^3 + k for k like (4n-1)^3 - 4m^2 that m , n are integers & no prime number that p is congruent to 1 modulo 4 count m, don't have any answer & it's proof is by ...
0
votes
0answers
16 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
74 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 ...
3
votes
0answers
37 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 ...
1
vote
1answer
25 views

Solving the Diophantine equation $ax + by = c$ using Maple [on hold]

I wrote a program in Maple called EEAsolve (I'm not sure how I can show everybody the code), and what it does is takes 3 parameters from $ax + by = c$: $a$, $b$, and $c$. When I run the program with ...
0
votes
0answers
20 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
40 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
57 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? ...
1
vote
0answers
47 views

Can anyone solve this without substitution

Find the values of $k \in \mathbb{Z}$ so that $\frac{234k}{641}$ has remainder $1$. Can anyone solve this without substitution?
9
votes
3answers
99 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
1answer
59 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, ...
0
votes
0answers
18 views

finding the logic behind the division method of hcf [on hold]

How does the division method of finding hcf work.should we consider that their exist a common factor that divides both the numbers.
2
votes
3answers
116 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
22 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$?
12
votes
5answers
967 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
16 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 ...
-2
votes
1answer
23 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
0answers
17 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
119 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
26 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
32 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
0answers
48 views

The sum of consecutive odd primes has at least three prime factors, not necessarily distinct [on hold]

Given the odd primes $3, 5, 7, 11, 13, 17, 19,\ldots, 2n-1$, prove that if $p$ and $q$ are adjacent odd primes in this list, then $p + q$ necessarily has $3$ prime factors. We do not require the ...
1
vote
3answers
51 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
155 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
381 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
0answers
12 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
31 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
11 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
26 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
67 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
23 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
47 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
0answers
54 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 { ...
4
votes
2answers
50 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
35 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
56 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?
1
vote
3answers
50 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
33 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
119 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
35 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 ...
-1
votes
0answers
10 views

Comparing coeficients of modulo arithmetic simultaneous equations

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?
5
votes
0answers
43 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 ...
2
votes
0answers
28 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
31 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 ...