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

learn more… | top users | synonyms (1)

1
vote
1answer
153 views

A question about prime divisors of Mersenne number $M_n= 2^n-1$ when $n$ is odd

Is this true that a prime divisor of a Mersenne number $M_n = 2^n-1$ when $n$ is odd, cannot be a Proth prime (i.e. a prime number of the form $2^mk+1$, where $k<2^m$)? If yes, how is it ...
1
vote
0answers
57 views

Show that if a and b are positive integers, then $(a + \frac12)^n + (b + \frac12)^n$ is an integer for only finitely many positive integers n. [duplicate]

I stumbled upon this problem when reading the resource provided by AoPS, on Number Theory. Here is the problem: Show that if $a$ and $b$ are positive integers, then $$\left(a + \frac12\right)^n + ...
2
votes
3answers
178 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.
0
votes
2answers
23 views

Complex numbers - Roots of unity - Proof that $G_d=G_n\cap G_m$

$$G_d=G_n\cap G_m$$ $$n,m \in \mathbb{N}$$ $$d=(n,m)$$ I know how to prove that $G_n\cap G_m\subset G_d$ but proving $G_d\subset G_n\cap G_m$ is giving me a hard time. I know $\exists ...
1
vote
0answers
103 views

Finding all positive integers $m,n$ such that $\frac{n^3+1}{mn-1}$ is an integer

Determine all ordered pairs $(m,n)$ of positive integers such that $\dfrac{n^3+1}{mn-1}$ is an integer. My work: $$\frac{n^3(m^3+1)}{mn-1}=\frac{(mn)^3-1}{mn-1}+\frac{n^3+1}{mn-1}.$$ Since, ...
2
votes
1answer
44 views

Theorem of Jacobi: $(2k+1)! + (-1)^{\eta} \equiv 0 \ (\operatorname{mod} p)$

The following is an exercise in "Certain Number-Theoretic Episodes In Algebra" by R. Sivaramakrishnan (in page 571). (Jacobi) Let $p$ be a prime of the form $4k+3$. Show that $$ (2k+1)! + ...
1
vote
2answers
66 views

Pigeonholing mod 4 points on plane.

I have the following problem as homework. Suppose there are 13 points in the plane, all with integer coordinates. Prove at least one quadrilateral with vertices on those points has a barycentre with ...
0
votes
2answers
41 views

Solve the equation [a]m[x]m=[b]m by finding convenient representatives for [a] and [b]

I need to solve this for $[6]_{10}[x]_{10}=[4]_{10}$. So if I am understanding the question correctly I need to solve for the values of $x$. So to do this I know that ...
22
votes
4answers
2k views

Sum of four squares not a prime

Let $ a, b, c, d $ be natural numbers such that $ ab=cd $. Prove that $ a^2+b^2+c^2+d^2 $ is not a prime. I am clueless on this one. I tried contradiction, but didn't get anywhere. Can you help? ...
22
votes
0answers
1k views

A very nice divisibility problem

A very hard problem, here it is: Prove that, if $2^{2^j} a + 1$ divides $c^{2^j}+1$ for fixed integers $a,c$ and all nonnegative integers $j$, then $a=1$ and $c=2^l$ for some odd positive integer ...
3
votes
1answer
204 views

Divisibility: $2^n a+1\mid c^n+1\ \forall n\in \mathbb{N}\implies a=1$

I have a very difficult problem that I cannot make any progress with. Here it is: Let $a,c$ be fixed positive integers. Prove that if $2^n a+1$ divides $c^n+1$ for all positive integers $n$, then ...
12
votes
1answer
152 views

Twelve Distinct Positive Integers

Let S be a set of twelve distinct positive integers such that for distinct a, b, c, and d in S, a + b ≠ c + d. Show that the largest element in S is greater than 56. I found some math competition ...
8
votes
5answers
226 views

If $(m,n)\in\mathbb Z_+^2$ satisfies $3m^2+m = 4n^2+n$ then $(m-n)$ is a perfect square.

I came across this question on another forum. The question is: $$ \text{If $m,n\in \mathbb{Z}_+$ such that $3m^2+m=4n^2+n$, then $(m-n)$ is a perfect square.}$$ I have managed to partially prove ...
-2
votes
1answer
70 views

Last Digit Of N^M

Given $N,M$ What is the best way to find last digit of $N^M$ if both $N,M$ Can be as large as $10^{18}$? EXAMPLE : if $N=2$ and $M=4$ then answer would be $6$.
0
votes
3answers
58 views

Let $a$ and $b$ be relatively prime integers. Prove $a^2$ and $b^2$ are prime as well. [duplicate]

Prime means the greatest divisor of that number is $1$ and itself. But where do I go from here?
4
votes
3answers
53 views

Graph of the last digit of $x^n$ - why is it symmetric when $n$ is even, and not when $n$ is odd?

I have discovered this fact: "The graph of the last digit of $x^n$ (where $x$ is positive) is asymmetrical if $n$ is odd, and symmetrical if $n$ is even." What is the logic behind this? For ...
-1
votes
1answer
70 views

Prove that $1$ has only one divisor

I'm looking at Euclid's Theorem (the infinitude of primes). The standard proof assumes there are finitely many primes (and proceeds to contradiction). It involves $P :=$ the product of all the ...
3
votes
2answers
394 views

How to prove infinitely many integer solutions for a relation?

I have the relation $x^2 + 4xy + y^2 = 1$. What I need to do is prove that it has infinitely many integer solutions. I started out by solving for $y$ and getting $y = -2x \pm \sqrt{3x^2 + 1}$ and ...
1
vote
4answers
30 views

If $a$ and $b$ are odd, prove $\gcd(a,b) = \gcd(\frac {\left| {a-b} \right |} {2}, b)$

Honestly I don't have a strong idea. I don't know where to even begin, I have considered that the $\gcd(a,b)$ is somehow less than $a-b$, but I'm not even sure why that would be the case.. Any help ...
2
votes
2answers
131 views

Using GCD/GCF to find number of intersections in a grid

The question I was trying to solve was: A rectangular floor $24×40$ is covered by squares of sides $1$. A chalk line is drawn from one corner to the diagonally opposite corner. How many tiles have ...
1
vote
0answers
35 views

Why do we need the extra assertion in this question?

Proposition: Let $2^i$ be the highest power of 2 dividing m, let a be odd and assume that $x^{m} \equiv a\space (mod\space 2 ^ {2i+1}$ ) is solvable. Then $\forall$ $j \geq$ 2i + 1, $x^{m} ...
2
votes
0answers
52 views

Partitions and divisor functions: what is known about their relations?

If $i\geq 1$ is an integer, we have the following integer valued functions (for any integer $n\geq 0$): \begin{align} p_i(n)&=\textrm{the number of }i\textrm{-dimensional partitions of ...
3
votes
2answers
717 views

Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or ...
3
votes
1answer
85 views

Prove a property of the divisor function

Let $q$ be an odd composite integer and $\sigma(q)$ the sum of the positive divisors of $q$. For what $q$ is it true that $$(\sigma(q)-q) \mid (q-1) \;?$$ If $q$ is prime, it is clear that it is ...
5
votes
3answers
153 views

Is there an easy way to prove that $3a^2+2=b^2$ does not have any rational solutions?

I am a physicist who needs to prove (for his research) that there are no $a,b\in\mathbb{Q}$ such that $3a^2+2=b^2$. Is there an easy way to do this?
0
votes
1answer
52 views

Probability that a number is a generator of a subgroup of $Z_p^*$ of order $q$

If $p$ is a random, large prime, what is the probability that a random element $x$ in $Z_p$ is a generator of a subgroup of $Z_p^*$ of order $q$, where $q$ is the largest number in the prime ...
3
votes
2answers
123 views

Eliminate numbers from $1,2,3. . .30$ such that the remaining sequence does not contain both $x$ and $2x$

BdMO 2014 nationals From the sequence 1,2,3. . . .30,pick another sequence of numbers such that if x is in our new sequence,then 2x is not there(or vice versa).What is the maximum number of terms ...
0
votes
1answer
31 views

How to prove these problems? (Operation on N)

If $m+n = m+k$, then $n=k$. If $mk = nk$ and $k\neq0$, then $m=n$. I'm not sure what t do. Do I have to use math induction or not? (Base on Peano system)
0
votes
1answer
45 views

Proving that an improved chinese remainder theorem algorithm returns $y^{d} \mod n$ *heavy modular math*

Suppose you're given the algorithm: $CRT(n,d_p,d_q,M_p,M_q,y)$ $x_p = y^{d_p} \mod p$ $x_q = y^{d_q} \mod q$ $x = M_pqx_p+M_qpx_q \mod n$ return $x$ If $d_K(y) = y^d \mod n$, $n = pq$, $d_p = d ...
2
votes
2answers
155 views

Gcd number theory proof: $(a^n-1,a^m-1)= a^{(m,n)}-1$ [duplicate]

Prove that if $a>1$ then $(a^n-1,a^m-1)= a^{(m,n)}-1$ where $(a,b) = \gcd(a,b)$ I've seen one proof using the Euclidean algorithm, but I didn't fully understand it because it wasn't very well ...
2
votes
2answers
65 views

Show that $17$ divides $6^{3n+2} - 2\cdot 29^n$ for all natural numbers $n$

Show that $17$ divides $6^{3n+2} - 2\cdot 29^n$ for all natural numbers $n$. I know that if $$17 \mid 6^{3n+2} - 2\cdot 29^n$$ then $6^{3n+2}$ is congruent to $2\cdot 29^n$ mod $17$. But how ...
1
vote
0answers
110 views

Proving that $\sqrt{4ab-1}=m^2$ is equivalent to $a=b$. where $a$ and $b$ are non zero integers

So the original question was to prove that if $4ab-1$ divides $4a^2-1)^2$, then $a=b$ where $a$ and $b$ are non zero integers. (IMO 2007) I proceed this way: $(4a²-1)²/(4ab-1)=q$ where $q$ is ...
1
vote
2answers
125 views

determining order of $x+1$ given the $x$ has order three

I was trying to expand $(x+1)^n$, then plug $x^3$ in to the expansion of the $(x+1)^n$, keep trying it until I get the order, are there any other ways? So if $x^3\equiv 1\pmod y$, how would I ...
-1
votes
2answers
49 views

GMAT #1 Number Operation [closed]

Which of the following is less than $\frac{1}{6}$? (A) 0.1667; (B) $\frac{3}{18}$; (C) 0.167; (D) 0.1666; (E) $\frac{8}{47}$.
1
vote
3answers
64 views

Modify the Fibonacci series [duplicate]

We know that Fibonacci Numbers start with 0 and next element is 1 and F(n)=F(n-1)+F(n-2) to find nth term where n>=2 and F(0)=0 F(1)=1 . But what if we suppose the first 2 terms of fibonacci series ...
4
votes
4answers
289 views

Solve $x^2+2=y^3$ using infinite descent?

just so this doesn't get deleted, I want to make it clear that I already know how to solve this using the UFD $\mathbb{Z}[\sqrt{-2}]$, and am in search for the infinite descent proof that Fermat ...
0
votes
2answers
28 views

Equality with mins headache

I came across the following equality while trying to prove this Multiplicative property of the GCD: $$\min\{a+c, b+d\} = \min\{a, b\} + \min\{c, d\} + \min\{a - \min\{a, b\}, d - \min\{c,d\}\} + ...
2
votes
0answers
54 views

arithmetic progression by Dirichlet

The arithmetic progression $a_N=(p-1)N+1$ contains infinitely many primes $q$ by Dirichlet. I have searched this part in wiki, but I din't get any relevant proof. Can any one prove it how $a_N$ ...
1
vote
3answers
108 views

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$.

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$. E.g. $p(7)=2\cdot3\cdot5$ (and $n=7$ is a solution). Let ...
1
vote
3answers
108 views

Divisibility test for $4$

Claim: A number is divisible by $4$ if and only if the number formed by the last two digits is divisible by $4$. Here's where I've gotten so far. Let $x$ be an $(n+1)$-digit number. So $x= ...
2
votes
1answer
59 views

Cyclic rearrangements of periods of certain periodic numbers

A student of mine observed the following \begin{align} \frac{1}{7}=0.\overline{142857} &\qquad \frac{2}{7}=0.\overline{285714} &\qquad \frac{3}{7}=0.\overline{428571} \\ ...
2
votes
1answer
57 views

Natural number to Rational number and at the end POULET number

Generalize / prove or disprove the following statement. For any prime $p$ $>5$ and prime $q$, we get infinite natural numbers $N$ such that $N$$= (q-1)/(p-1)$. If $N$ is rational, instead of ...
1
vote
3answers
201 views

If $\gcd(a, b) = 1$ and if $ab = x^2$, prove that $a, b$ must also be perfect squares; where $a,b,x$ are in the set of natural numbers

Problem: If $\gcd(a, b) = 1$ and If $ab = x^2$ ,prove that $a$, $b$ must also be perfect squares; where $a$,$b$,$x$ are in the set of natural numbers I've come to the conclusion that $a \ne b$ and ...
0
votes
1answer
285 views

If $\gcd (a,b)=1$, and $\gcd(a,c)=1$, then $\gcd (a,bc)=1$ [duplicate]

If $\gcd (a,b)=1$, and $\gcd(a,c)=1$, then $\gcd (a,bc)=1$ Help proving this? I'm really confused how to go about it..
0
votes
3answers
299 views

Incongruent solutions to $7x \equiv 3$ (mod $15$)

I'm supposed to find all the incongruent solutions to the congruency $7x \equiv 3$ (mod $15$) \begin{align*} 7x &\equiv 3 \mod{15} \\ 7x - 3 &= 15k \hspace{1in} (k \in \mathbb{Z}) \\ 7x ...
2
votes
3answers
219 views

If a and b are odd integers, then $8\mid (a^2-b^2)$

Prove: If $a$ and $b$ are odd integers, then $8\mid (a^2-b^2)$ So far I have: $$8\mid \left((2n+1)^2-(2m+1)^2\right)\Longleftrightarrow 8\mid \left(4n^2+4n+1-4m^2-4m-1\right) $$ Is this right so far? ...
3
votes
1answer
35 views

Prove that if $R$ is not prime then $R$ must have a prime factor $q$ that is larger than $p_n$.

This is a modification of my previous post here which has completely different meanings/solutions Given that $R = p_1p_2\cdots p_n + 1$ where $p_1 < p_2 < \cdots < p_n$ and $p$ are ...
0
votes
2answers
56 views

Find all numbers $a < 20$ so that $6a \equiv 16 \pmod {20}$

Find all numbers $a < 20$ so that $6a \equiv 16 \pmod {20}$ So far I have that $20 \mid 16-6a$ which implies $16 - 6a = 20q$ for some integer $q$. Then $8-3a=10q$ which means that $8 \equiv ...
1
vote
3answers
135 views

Prove: If x≡y (mod m), then (m,x) = (m,y)

The question is to prove if x≡y (mod m), then (m,x) = (m,y). I think that I should start by showing that m|x-y and by the definition of division x-y=mq for some integer q. If I let d=(m,x) then I know ...
0
votes
2answers
37 views

Find a test for divisibility

The task is to find a test for divisibility by 6. Does it suffice to say that since 6=2*3, the test for divisibility by 6 must satisfy the tests for divisibility by both 2 and 3. So the resulting rule ...