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

learn more… | top users | synonyms (1)

4
votes
2answers
68 views

$n$ is a positive integer and let $p$ be a prime divisor of $n^{54}+n^{27}+1$. Prove if $p \ne 3$ then $ord_p(n) = 81$ and $p \equiv 1 \pmod {81}$

more exam practice questions. I feel like I am making some pretty futile attempts here and would greatly appreciate some insight and help! Here is what I have so far: First of all I think the ...
1
vote
1answer
80 views

number partitioning such that the pats are prime

For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.
3
votes
2answers
61 views

Show that if $R_n$ is prime then $n$ must be prime.

this is an exam practice question: For each positive $n$ define $R_n = \frac{1}{9}(10^n-1) $ (so that in the usual base 10 notation, $R_n = 111,\ldots,1$ where there are n digits). Show ...
3
votes
4answers
276 views

Is $ n^2-14n+24 $ a prime number?

How many are those positive integers n such that Is $ n^2-14n+24 $ is prime ? I have tried to solve this problem by putting different values of natural number . Is it a right way ?
2
votes
2answers
180 views

7 digit number consisting of 7s and 5s

Find all the 7 digit numbers that have only 5 and 7 as their digits and divisible by both 5 and 7. I have no clue how to use divisibility of 7 to solve this problem. DO i need to check all the 64 ...
0
votes
2answers
64 views

Showing work for Gcd

I have these two pairs I'm supposed to find the GCD of as a linear combination: $(33,44)$ and $(101,203)$. Now, I have the answers but I have a professor that is a real fricken stickler about showing ...
5
votes
1answer
107 views

Prove that $n\mid \phi(a^n-b^n)$

In this post, I asked how to prove $n\mid \phi(2^n-1),(n\in \mathbb N)$. @Amr and @Abhra Abir Kundu proved more: they proved that $n\mid \phi(a^n-1),(a,n\in \mathbb N).$ The method is very nice. I ...
2
votes
2answers
80 views

show that the even numbers 2k+2,2k+4,…,4k,4k+2 are congruent mod m to…

(first post, hello!) I'm having a bit of trouble with the following problem: let k be a positive integer and let $m = 4k + 3$ show that the even numbers $2k+2, 2k+4,..., 4k, 4k+2 $ are ...
1
vote
2answers
84 views

About Pythagorean triple

I have a question about number of primitive Pythagorean triples. Is there infinite number of primitive Pythagroean triples for which the acute angles of the corresponding triangles are, for any given ...
3
votes
3answers
129 views

How prove this $\binom{n}{m}\equiv 0\pmod p$

let $p$ is prime number,and such $p\mid n,p\nmid m,n\ge m$ show that $$p\>\Big|\>\binom{n}{m}$$ I know that: if $p$ is prime number,then $$\binom{n}{p}\equiv \left[\dfrac{n}{p}\right] \pmod ...
1
vote
0answers
64 views

Show that $x^2\equiv a \pmod {2^n}$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$

Show that $$x^2\equiv a \pmod {2^n}$$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$ Actually, the question I had to solve was more complicated something like this: $x^2\equiv a ...
0
votes
4answers
141 views

name of rule that says: x(x+1) is even number

What is the name of the rule that states that $x(x+1)$ is always even number? Mathworld says: "The product of an even number and an odd number is always even" But it does not state any name: ...
2
votes
0answers
35 views

Is it true that $\sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}$?

Given $q \in \mathbb N$, $q\geq 2$ is it true that \begin{equation*} \sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}? \end{equation*} Here $H_q(x) = x\log _q(1/x) + (1-x)\log _q(1/(1-x))$ is the ...
2
votes
2answers
193 views

Prove that every odd natural number divides some number of the form $2^n - 1$ [duplicate]

Suppose that $m$ is an odd natural number. Prove that there is a natural number $n$ such that $m$ divides $2^n -1$. I have absolutely no idea how to tackle this; any assistance would be welcome.
3
votes
2answers
199 views

Combinatorial Proof Of A Number Theory Theorem--Confusion

I came across a combinatorial proof of the Fermat's Little Theorem which states that If $p$ is a prime number then the number ($a$$p$-$a$) is a multiple of $p$ for any natural number $a$. Let me ...
2
votes
1answer
78 views

Calculating 6 decimal digits of $3^{\sqrt2}$ using a calculator.

How can we calculate $3^{\sqrt2}$ to 6 decimal digits, using only a semi-basic calculator (Which has the square root too) and a pen and paper? I asked this question from my teacher and he ...
0
votes
1answer
57 views

What is the identity for ab=2ab (mod 7)?

Using elements 1, 3, 5 write out a Cayley table. The operation for the table is ab = 2ab. For example 5*4= 5*4*2= 40 congruent to 5 (mod 7). What is the identity for this table?
0
votes
2answers
32 views

Smallest integer x s.t. x! congruent to 0 (mod 216)

By guess and check I found x to be 9, but is there a more general way to solve this?
2
votes
1answer
462 views

Pell's Equation through Continued Fractions

Use continued fractions to find the minimal solution to $x^2-11y^2=1$. I know that $\sqrt{11}=3+\frac{1}{3+\frac{1}{6+\frac{1}{3+...}}}$ I took $\sqrt{11}=3+\frac{1}{3+\frac{1}{6+\sqrt{11}}}$ and I ...
1
vote
2answers
102 views

Find the smallest integer x s.t. x congruent to 1 (mod 1,2,3,4,5,6,7,8,9,10)

Don't really understand this question. If this is asking to find an x for each mod then the answer would be just be x+m...If this is asking to find an x that satisfies all mods, then this cant be ...
2
votes
1answer
140 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
0
votes
2answers
74 views

How to solve $(2x+2, 6x) = x+1$

I'm looking at an old discrete mathematics test preparing for my test tomorrow and one question says solve for $x$ and gives the above. I'm thinking that this is the $\gcd(2x+2, 6x)$ but have never ...
0
votes
2answers
65 views

Solving $4^{667} ≡ x \pmod{13}$ without Eulers totient theorem or CRT

Does anyone know any efficient ways to solve this without Euler's Totient Theorem or Chinese remainder theorem?
2
votes
2answers
37 views

How to solve $7200a+720b+72c=1000x+340+y<10000$?

What is the easiest way to solve $7200a+720b+72c=1000x+340+y<10000$ where all variables are one digit natural numbers? Trial and error method seems to be tedious.
-3
votes
3answers
120 views

Prove that $S=1+2+3+…+n$ is not a prime number

I need help: I don't know how to prove that $S=1+2+3+\cdots+n$ is not a prime number, for any $ n \ge 3 $. Thank you in advance.
0
votes
2answers
69 views

Prove that something is a divisor of something else

For every $a > 1$ and $n$ an element of the natural numbers, we have that $a - 1$ is a divisor of $a^n - 1$. Or written with symbols: $$\forall \ a > 1 ∧ n \in \mathbb{N}: (a−1) \ | \ a^n −1.$$ ...
0
votes
1answer
51 views

Prove that if $b$ and $c$ are odd, then ${a\choose bc}={a\choose b}{a\choose c}$

I tried to use the reciprocity law to prove it, but neither $a$ nor $bc$ is odd prime. Then, I tried by definition, ${\large{a\choose bc}}=a^{\large{\frac{bc-1}{2}}} \pmod{bc}$. ${\large{a\choose ...
2
votes
2answers
78 views

Showing Inequality using Gauss Function

If $\alpha, \beta\in \Bbb{R}$ and $m, n\in \Bbb{N}$ show that the inequality $[(m+n)\alpha]+[(m+n)\beta] \ge [m\alpha]+[m\beta]+[n\alpha+n\beta]$ holds iff m=n I thought that we have to ...
1
vote
0answers
67 views

Pythagorean triples for a given hypotenuse

Is there a deterministic method for generating all of the Pythagorean triples {a, b, c} for a given hypotenuse c?
0
votes
1answer
42 views

Question about 2^mersenne number

We are given that $2^n \equiv 2\ \pmod n $. If $m=2^n -1$, prove that $2^m \equiv 2\ \pmod m$ My first instinct is that we can somehow use fact that $2^n\equiv 1 \ \pmod m$ and use that, but I havent ...
1
vote
2answers
104 views

Let p be an odd prime number and let n be a quadratic nonresidue modulo p. Prove that

$$ \sum_{\substack{d\mid n\\d>0}} d^{\frac{p-1}{2}}\equiv0\pmod{p} $$ I've tried using the fact that the sum divides evenly into p to prove it directly. But I just can't seem to figure out a ...
1
vote
1answer
329 views

Let p be an odd prime number. Prove that [duplicate]

$$\left(\frac{1\cdot2}{p}\right) + \left(\frac{2\cdot3}{p}\right) + \left(\frac{3\cdot4}{p}\right) +\ldots+ \left(\frac{(p-2)(p-1)}{p}\right) = -1$$ Note: $\left(\frac{a}{b}\right)$ represents the ...
6
votes
3answers
183 views

Show that prime $p=4n+1$ is a divisor of $n^{n}-1$

Show that the prime number $p=4n+1$ is a divisor of $n^{n}-1$ Ok, the question itself is simple as hell, but I couldn't think of a simple way to solve this question. I tried to solve the ...
2
votes
1answer
109 views

Estimating total number of twin primes

Taking my notation from a previous question Define a function $P_6$ as $$P_6(n)=\begin{cases} 0, \ \ 6n-1 \not\in \mathbb P \wedge 6n+1 \not\in \mathbb P \\ 1, \ \ (6n-1 \not\in \mathbb P \wedge ...
1
vote
1answer
132 views

Prove that $\left( \frac{p-1}{2} \right)! \equiv (-1)^n \mod p$, $n$ is quad. nonres. of $p$ $< p/2$.

Let $p$be a prime number with $p \equiv 3 \mod 4$. Prove that $\left( \frac{p-1}{2} \right)! \equiv (-1)^n \mod p$ where $n$ is the number of positive integers less than $p/2$ that are quadratic ...
0
votes
1answer
24 views

Number satisfying certain conditions

Let $a,b,c,d \in N$, such that $a>b,c>d$, $a\neq c$ and $\sqrt{a} - \sqrt{b} = \sqrt{c} -\sqrt{d}$. Is it true that all $a,b,c,d$ must be squares? Thanks
0
votes
1answer
59 views

RSA Public key System

In RSA public key system, how does one ensure that the receiver is getting the message from the intended sender? How can the receiver rule out messages from eavesdroppers I know that the receiver has ...
1
vote
1answer
383 views

Proof by contradiction Let $n \in \mathbb{N}$. Any odd prime factor $p$ of $n^2 +1$ has the form $p = 4k+1$ for some integer $k \geq 0$.

Let $n \in \mathbb{N}$. Any odd prime factor $p$ of $n^2 +1$ has the form $p = 4k+1$ for some integer $k \geq 0$. Proof using contradiction. I am a little bit stuck, can someone help me get started ...
7
votes
1answer
133 views

$\left( \frac{1 \cdot 2}{p} \right) + \left( \frac{2 \cdot 3}{p} \right) + \cdots + \left( \frac{(p-2)(p-1)}{p} \right) = -1$

Let $p$ be an odd prime number. Prove that $$\left( \frac{1 \cdot 2}{p} \right) + \left( \frac{2 \cdot 3}{p} \right) + \left( \frac{3 \cdot 4}{p} \right) + \cdots + \left( \frac{(p-2)(p-1)}{p} \right) ...
2
votes
3answers
108 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
-1
votes
1answer
29 views

simple algebraic inequality question

For any $a,b,c$ such that $0 < a < b < c$ , prove/disprove: $\frac{b}{a+b} + \frac{c}{b+c} - \frac{c}{a+c} - \frac{1}{2} > 0$
1
vote
1answer
402 views

Let m ≥ 2 be an integer. Show that if a is an integer such that gcd(a, m) = ̸= 1, there exists [x]* in Zm such that [a]·[x]=[0].

--> * [x] is a non-zero congruence class I've gotten this far: since d|m, m=kd, k=m/d [k] is non-zero since 0 < k < m. [a] . [k] = [0] because... I'm not sure how to prove this.
0
votes
1answer
561 views

Let n∈ℕ. Suppose that p is an odd prime number that divides n^2+1 Show that if p=4k+3 for some integer k≥0, then n^(p−1)≡−1(modp).

Let $n \in \mathbb N$. Suppose that $p$ is an odd prime number that divides $n^2+1$. Show that if $p=4k+3$ for some integer $k \ge 0$, then $n^{p−1}\equiv−1 \pmod p$. The question says to use "if ...
1
vote
0answers
73 views

How to solve the diophantine equation:$ xa^3+yb^3=c^3$

Let $a,b,c,x,y \in \mathbb{Z}> 1$. Any hint on how to solve of the diophantine equation $ xa^3+yb^3=c^3$?
1
vote
1answer
224 views

Number Theory Help: Eulers phi function, LCM, and Modulos

Assume that $r$ and $s$ are relatively prime positive integers and that $n =rs$. Let $m = \mbox{lcm}(\phi(s), \phi(r))$ and assume that $\mbox{gcd}(a,n)=1$. Prove $$a^m \equiv 1 \bmod{r} \mbox{ ...
8
votes
1answer
110 views

Conjecture on integer solutions to the equation $ (ab + 1) \mid (a^{2}+b^{2})$

Inspired by the egregious problem in IMO 1988, I simulated the integer solutions to the equation $$ (ab + 1) \mid (a^{2} + b^{2}) \tag{*}$$ for $1 \leq a, b \leq 3000$ and conjectured that every ...
0
votes
1answer
133 views

General technique to find largest number that can't be written as a sum of multiples of a given list of numbers

I am given a set of numbers $(n_1, n_2, ...)$ with $n_1 < n_2 < ...$ and I want to know what the largest number is that can't be written as $a_1*n_1 + a_2*n_2 + ...$ The set of numbers is always ...
3
votes
1answer
54 views

Given positive integers $a,b,n,t$ with $n>t$ and the relations $n-1=a(t-1)$ and $an=bt$, prove that $b>t$.

Given positive integers $a,b,n,t$ with $n>t$ and the relations $n-1=a(t-1)$ and $an=bt$, prove that $b>t$. When $n$ is prime, $an=bt$ implies $n\mid b$ or $n\mid t$, so $n\mid b$ since $t<n$, ...
13
votes
2answers
269 views

Can my MSE reputation be any positive integer?

As far as I know there are five kinds of vote $+2$ for an edit $-2$ for a downvote $+10$ for an answer $+15$ for an accepted answer $+5$ for a question Suppose that this is true. Can a MSE ...
0
votes
2answers
367 views

Given remainders, determine smallest possible number of eggs in the basket

I have a question about "Elementary Number Theory - 6th Edition", written by David M.Burton. In page 83 #9, I don't know how to solve it. The problem is, The basket-of-eggs problem is often ...