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

learn more… | top users | synonyms

2
votes
1answer
21 views

Prove for any integer $N$ that there exists $n > N$ where $n!-1$ is not a prime

I was thinking about Euclid's proof of the infinitude of primes and the fact that we could make the argument about $n!-1$ instead of $n!+1$ when I wondered if it would be easy to prove that for any ...
0
votes
1answer
29 views

$\mathrm{lcm}(b,c)$ from $\mathrm{lcm}(a,b)$ and $\mathrm{lcm}(a,c)$

Given that lcm$(a,b)=60$ and lcm$(a,c)=270$, find lcm$(b,c)$ I believe you're supposed to use the rule lcm$(a,b)=p_1^{\text{max}(r_1,s_1)}\cdots p_m^{\text{max}(r_m,s_m)}$ Here's my work so far: ...
0
votes
1answer
9 views

“Multivariable” version of this lemma about showing analytically that a number is irrational.

Lemma: let $\alpha \in \mathbb{R}^+$ and $p_1,p_2,\dots, q_1, q_2, \ldots \in \mathbb{N}$ such that $\left|\alpha q_n - p_n \right| \neq 0$ for all $n \in \mathbb{N}$ and $$ \lim_{n \rightarrow ...
2
votes
1answer
49 views

Could someone take a crack at this number theory problem?

The question is stated as follows: If $\mathrm{gcd}(a,m)=1$ and $X$ is a complete residue system $\bmod m$, then the set obtained by multiplying each member of $X$ by $a$ is also a complete residue ...
1
vote
1answer
29 views

Numbers that can be represented by 32 bits

A typical computer 'word' is either 32 or 64 bits long. For each of the following encoding, determine the range of numbers (in base 10) that can be represented with (i) 32 bits and ...
0
votes
1answer
30 views

How to prove $V(5x^2+6xy+2y^2-2yz-z^2)$ is empty

Let $V/\mathbb{Q}$ be the projective variety $V:5x^2+6xy+2y^2=2yz+z^2$. I want to prove $V(\mathbb{Q})$ is empty. Given $[x,y,z]$ in $V$, WLOG assume $x,y,z\in \mathbb{Z}$ and $\gcd(x,y,z)=1$. ...
-1
votes
1answer
25 views

Find the number which is the sum of different consecutive integers

Problem: Find $n$ such that $n>200$ $n$ can be written like the sum of of $5$, $6$, and $7$ consecutive integers I'm currently studying modular arithmetic so I tried to solve witusoinh it. ...
3
votes
1answer
41 views

Relationship between increasing integer sequences

Suppose that $X\cap Y=\emptyset$, that $X\cup Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to X$ respectively $\Bbb N\to Y$. Further, suppose that there are straight line ...
0
votes
2answers
34 views

How to solve this quartic congruence?

Given $x^4 + 36x^3 - 19x^2 + 11x - 14 \equiv 0 \pmod{5}$. How would one go about solving such an congruence equation? Maybe it's possible to reduce this to a quadratic congruence? I can't figure it ...
1
vote
2answers
30 views

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$. The hint says that because $t_1^2+t_2^2+ \cdots +t_n^2 = t_n(3n^3 + 12n^2 + 13n + ...
1
vote
2answers
33 views

Criteria for the existence of zero-divisors and idempotent elements in the integers modulo $n$

I need help in establishing or at least deciding the validity of the following two criteria: There are in the ring $Z_n$ non-trivial zero divisors if only if $n$ is divisible with some square. ...
7
votes
4answers
62 views

Proof: if p is prime, and 0<k<p then p divides ${p \choose k}$

Question : IF p is prime, and 0< k< p show that $ p | {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)... (p-(k-1))(p-k)! \over (p-k)! k(k-1)(k-2)...3.2.1}$$ Now the (p-k)! ...
1
vote
4answers
68 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
0
votes
3answers
26 views

Find the Inverse Modulus using Euclid's algorithm

I asked this before, but unfortunately, I didnt know the methods, nor was the questions phrased properly. Find the inverse of $4258 \pmod{147}$ Using Euclidean Extended Algorithm. Begin By Stating ...
4
votes
4answers
218 views

Find how many positive divisors a number has. What would you do?

Recently I learned an amazing thing. Suppose you are given a number and you have to find how many positive divisors it has. What would you do ? Solution: Suppose you select $12$. It has ...
1
vote
3answers
31 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
56 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
26 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
25 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$, ...
7
votes
3answers
347 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
35 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
75 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
40 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
27 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
59 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
103 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
65 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
19 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
119 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$?
19
votes
7answers
2k 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
17 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
24 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
22 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
120 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
27 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
36 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
157 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
383 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
13 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
33 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
12 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 ...