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

learn more… | top users | synonyms

7
votes
6answers
3k views

If $n$ is an odd natural number, then $8$ divides $n^{2}-1$

I am trying to show that if $n$ is an odd natural number, then $8$ divides $n^{2}-1.$ I was able to prove that because I know that if $n$ is an odd natural number, then $n^{2}$ can be writen as $8k+1$ ...
2
votes
4answers
117 views

Mixture of materials problem: What is the right ratio?

Consider three types of sugar priced at 10, 12 and 18 per kg be mixed to form a mixture of price 14 per kg. Find the ratio in which three types of sugar were mixed. The answer is 3:4:5
1
vote
3answers
101 views

If $a^n \equiv b \pmod m$ and $b^n \equiv c \pmod m$, is it true that $(a^n)^n \equiv c \pmod m$?

If $a^n \equiv b \pmod m$ and $b^n \equiv c \pmod m$, is it true that $(a^n)^n \equiv c \pmod m$? From testing cases it seems to be true, but I'm unsure of how to prove this.
1
vote
2answers
244 views

Understanding congruence and using the notation correctly

I am working on the following problem presented in a text: Find the remainder when $3^{1000}$ is divided by 13. I have just been introduced to the notation for saying that $a\equiv b \pmod{n}$. ...
2
votes
0answers
71 views

Solving linear inequalities over rings

The concrete problem: for any given $N\ge 1$ I have a system of $2^N-1$ linear inequalities over $\mathbb{Z}_6^N$ which looks like this: for every nonempty $S\subseteq[N]$ there is some ...
5
votes
0answers
135 views

Question about a proof on p70 in Cassels' Local Fields

I'm trying to read the proof of COROLLARY. The only solutions of $x^2+7=2^m$ ($x,m \in \mathbb{Z}$) (6.15) have $m=3,4,5,7,15$. I don't see why there could be a + in $y\pm \alpha$ ...
0
votes
1answer
110 views

Matching Given Two Sets of Preferences

Suppose that there is a program that matches newly hired employees to vacancies within an organization. After interviewing all managers who have vacancies, applicants score (NOT RANK) the positions ...
2
votes
2answers
322 views

If all of $p, p + 2, p + 6$ and $p + 8$ are prime, then $p \equiv k \pmod d$

How do I answer this question? Find the largest value of $d$, and the corresponding value of $k$, for which the following theorem is true: If all of $p, p + 2, p + 6$ and $p + 8$ are prime, ...
2
votes
3answers
621 views

Prove that there are no integer solutions to $3m^2-1=n^2$.

How do I answer this? Prove that it is impossible to find any integer $n$ such that $n^2 \equiv 2 \pmod 4$ or $n^2 \equiv 3 \pmod 4$. Hence or otherwise, prove that there do not exist integers ...
1
vote
4answers
2k views

Fastest Method to solve this average problem

average of A and B is 71; of B and C is 76; of A and C is 79. How to find the average of A,B,C. I know the way of solving this problem using equations.But it takes time.So wanted to know if any other ...
4
votes
2answers
720 views

Is any odd natural number less than the sum of its factors?

A perfect number is an integer $n$ greater than $1$ that equals the sum of its factors, excluding $n$ itself. For example, $6 = 1 + 2 +3 $ so $6$ is perfect. It is unknown whether there are any odd ...
9
votes
3answers
2k views

If an integer is not divisible by 2 or 5

I have found this statement ,can you help me to prove this. If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit. OBJECTIVE: Now ...
16
votes
5answers
758 views

Puzzle: Cumulative Sum Divisible by 10

If we sum the first $4$ positive integers, we get $4 + 3 + 2 + 1 = 10$, which I think is pretty cool. I'm interested in seeing solutions to the following puzzle: If we take the cumulative sum of the ...
2
votes
2answers
179 views

Proving $2^{\varphi(n)}\ge n$

To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$ I can't follow the proof from http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html ...
3
votes
3answers
217 views

Recovering a number from a remainder list

Consider the following list of equations: $$\begin{align*} x \bmod 2 &= 1\\ x \bmod 3 &= 1\\ x \bmod 5 &= 3 \end{align*}$$ How many equations like this do you need to write in order to ...
2
votes
3answers
160 views

Solve $V_1+V_2+\cdots+V_k=A, V_1^2+V_2^2+\cdots+V_k^2=B$ in positive integers

There have been changes made to the second equation in the pair that will be worth looking at. All values for the solutions must be non-zero positive integers (natural numbers). Please note, all ...
6
votes
1answer
186 views

Line in a proof on p69 in Cassel's Local Fields

I'm trying to read the proof of LEMMA 6.1 (Nagell) Let $u_n$ be defined by $u_0=0$, $u_1=1$ and $u_n=u_{n-1}-2u_{n-2} \hspace{20pt} (n\geq 2)$. Then $u_n=\pm1$ only for $n=1,2,3, ...
5
votes
4answers
329 views

Does this polynomial evaluate to prime number whenever $x$ is a natural number?

I am trying to prove or disprove following statment: $x^2-31x+257$ evaluates to a prime number whenever $x$ is a natural number. First of all, I realized that we can't factorize this ...
4
votes
2answers
747 views

Prove that $x^{2} \equiv -1$ (mod $p$) has no solutions if prime $p \equiv 3\pmod 4$.

Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$ Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$. I know this problem has something to do with Fermat's Little ...
1
vote
1answer
277 views

What is the intuition behind the Fermat-Euler's Theorem?

Can someone give me an intuition behind the working of Fermat-Euler's theorem? I am not looking for definition nor for proof (I know both of them). $$a^{\phi(p)} \equiv 1 \pmod p$$ This is what I ...
3
votes
1answer
75 views

Why are generators of $Z^{*}_p, p=c \cdot 2^k + 1$ so small?

I was implementing NTT for long integer multiplication and thus searched for generators of several $Z^{*}_p$ groups where $p=c\cdot 2^k + 1$. I used the algorithm described in Wikipedia which uses ...
4
votes
1answer
216 views

Primitive root modulo $p$

I am currently trying to find a primitive element of the multiplicative group of field $GF(p)$. Since the numbers are relatively small, I know the factorization of $$\phi(p)=p-1 = {p_1}^{k_1} ...
2
votes
1answer
486 views

Decrypting a Message Encrypted in RSA Using Two Coprime Encryption Keys

The last question of our number theory final review is as follows: The same plaintext $P$ is encrypted in RSA using two coprime encryption keys $e_1$, $e_2$. Show how this message can be decrypted ...
1
vote
1answer
251 views

$n$-power residues theorem and its use

I'd love your help with the following problem: Let $p$ be an odd prime. I need to show that for any $a$ prime to $p$, either $a^{\frac{(p-1)}{2}}\equiv 1\pmod p$ or $a^{\frac{(p-1)}{2}}\equiv ...
7
votes
4answers
675 views

Seemingly invalid step in the proof of $\frac{a^2+b^2}{ab+1}$ is a perfect square?

Recall the famous IMO 1988 question 6: Suppose that $\displaystyle\frac{a^2+b^2}{ab+1}=k\in\mathbb{N}$ for some $a,b\in\mathbb{N}$. Show that $k$ is a perfect square. Solutions can be found: ...
1
vote
2answers
1k views

Finding all the primitive roots modulo $25$ and $26$- methods and theorems.

I'd really love your help with the following problem. I'm trying to use couple of theorems that I know, but I'm not sure if I'm allowed to and if I'm doing it correctly. The question is simple: I ...
3
votes
0answers
63 views

Lucasian Criterion for the Primality of $3\cdot 2^n+1$

Note : This problem has no specific source Def : Let's define number $N$ as : $N=3\cdot 2^n+1$ Def : Let's define starting seed $S$ as : $S = \begin{cases} 32672, & \text{if } n\equiv 1 ...
18
votes
5answers
4k views

Highest power of a prime $p$ dividing $N!$

How does one find the highest power of a prime $p$ that divides $N!$ and other related products? Related question: How many zeros are there at the end of $N!$? This is being done to reduce ...
-1
votes
1answer
121 views

Integer combination of $V\subseteq\mathbb{Z}^n = (1, 1, 1, \ldots)$?

What are the subsets $V\subseteq\mathbb{Z}^n$ such that there is an integer combination of vectors in $V$ equal to $(1, 1, 1, \ldots)$? (where $n \in \mathbb{Z}^+$ and $\mathbb{Z}^n$ is the n-ary ...
7
votes
1answer
2k views

If $2^n+1$ is prime, why must $n$ be a power of $2$?

A little bird told me that if $2^n+1$ is prime, then $n$ is a power of $2$. I tend not to trust talking birds, so I'm trying to verify that statement independently. Suppose $n$ is not a power of $2$. ...
3
votes
2answers
191 views

Help manipulating Wilson's Theorem. [duplicate]

Possible Duplicate: Closed form for $(p-n)!\pmod{p}$ where $p$ is prime I would like to use Wilson's Theorem to compute $(p - 4)! \mod p$ I've gotten as far as $(p - 4)! \cdot (p-3) ...
3
votes
2answers
103 views

Is there a way to simplify this expression $(a + b) \% c$

I am having an expression of the form $ (a+b) \% c $ where a,b,c are positive integers greater than or equal to zero (natural numbers). $\%$ indicates modulo operation. Also, there is a restriction ...
10
votes
3answers
1k views

Solving $x^3-y^3=xy+61$ in integers

I'm trying to solve the following equation: $$x^3-y^3=xy+61$$ I got: $$(x-y)(x^2+xy+y^2)=xy+61$$ But I can't go any further. I am looking for a solution in integers. I need some hints to proceed, ...
3
votes
1answer
169 views

Check for prime

I know there are a lot of questions on this board about finding prime numbers, and I've gone through a bunch of them. I even came across this interesting site about primes: ...
0
votes
2answers
364 views

Solving an inequality modulo 1

In essence, my problem boils down to finding all $i$ that satisfies this inequality ($n$ is constant): $$ \frac{n}{i} \text{ (mod 1) } < \frac{n}{i+1} \text{ (mod 1) for }n,i\in\mathbb{N}, i < ...
4
votes
4answers
270 views

If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$.

I am trying to prove this: $n$, $a$ and $b$ are positive integers. If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$. I want to prove this by contradiction, and I ...
1
vote
3answers
86 views

Prove is $n \in \mathbb{N}$ and is $p$ is prime such that $p|(n!)^2+1$ then $(p-1)/2$ is even?

Can anyone help me prove if $n \in \mathbb{N}$ and is $p$ is prime such that $p|(n!)^2+1$ then $(p-1)/2$ is even? I'm attempting to use Fermats little theorem, so far I have only shown $p$ is odd. I ...
1
vote
3answers
73 views

Given $N$, $a$, and $b$, does there exist an $x$ such that $b$ divides $N-ax$?

Given $N$, $a$, $b$ and condition that all are positive integers, how to find whether any positive integer $x$ exists such that $b|(N-ax)$. And if any such $x$ exists how to calculate minimum value ...
1
vote
2answers
100 views

finding the quadratic irratonality of simple continued fractions

For instance: find the quadratic irrationality of the simple continued fraction [1;2,3]. I have a handful of these problems to do, so any walk-through of one problem should give me the general idea ...
6
votes
6answers
563 views

How do I show that the sum $(a+\frac12)^n+(b+\frac12)^n$ is an integer for only finitely many $n$?

Show that if $a$ and $b$ are positive integers, then $$\left(a +\frac12\right)^n + \left(b+\frac{1}{2}\right)^n$$is an integer for only finitely many positive integers $n$. I tried hard but ...
-1
votes
1answer
145 views

Prove or give a counter-example for the inequality

Prove or give a counter-example for the following: $\frac{2}{\gamma}[\sqrt{(1+\gamma (n-1))(1+\gamma (s -1))}-(1+\gamma (s -1))] \leq n-s$ where $n,s$ natural numbers with $n \geq 2$, ...
3
votes
4answers
98 views

Congruences and proving

Prove that for $a,b \in Z$ such that $17\mid 2a+3b$, it is true that $17\mid 7a+2b$. Could you please check my answer? Here it is: For sure $17b\equiv 0 \pmod{17}$. Then Also ...
2
votes
1answer
101 views

If $\alpha \in \mathbb{Z}(\omega)$, show that $\alpha$ is congruent to either $0, 1$ or $-1$ modulo $1-\omega$.

If $\alpha \in \mathbb{Z}(\omega)$, show that $\alpha$ is congruent to either $0, 1$ or $-1$ modulo $1-\omega$. Exercise 1 page 134 in the book 'A Classical Introduction to Modern Number Theory' of ...
1
vote
1answer
115 views

Number of couples of integers with a given lcm

How to find the number $P$ of integers $(n,m)$ such that $\operatorname{lcm}(n,m) = k$? Only $k$ is given. I only find the number of $n$ such that $\operatorname{lcm}(n,k) = k$. Can anyone help me ...
0
votes
2answers
310 views

Moving last digit to first

Is it possible to find all positive integers $n$ such that if we move its last digit to the first digit, we get $2n$? I.e $2(a_m\cdot 10^m+\ldots +a_0)=a_0\cdot 10^m+a_m\cdot 10^{m-1}\cdots+a_1$
1
vote
2answers
217 views

Proof of equation in modular arithmetic

Can anybody prove that the following equation is true? $$7^n + 9^n \equiv 0 \pmod {11}\quad\text{where}\quad n\equiv 5 \pmod{10}$$ Thanks in advance.
0
votes
0answers
255 views

proof by infinite descent of a Diophantine equation

Show that the Diophantine equation $x^{4} - y^{4} = z^{2}$ has no solutions in nonzero integers using the method of infinite descent. Thanks for any help on this proof. Infinite descent has me kind ...
0
votes
2answers
465 views

Solving quadratic residue

Suppose we have $25x^2 + 70x + 37 \equiv 0 \pmod{13}$. Since it doesn't factor we obviously have to subtract/add $(ax + b)$ from both sides of the congruence. However I'm getting different answers. ...
1
vote
1answer
101 views

Proving $\alpha : \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$ is injective.

Let $m$ and $n$ be relatively prime positive integers. Define $\alpha : \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$ by $\alpha([a]_{mn}) = ([a]_m,[a]_n)$. Prove that $\alpha$ is ...
0
votes
4answers
597 views

Is $\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$?

Let $a$,$b$,$c$ and $d$ be four natural numbers such that $\gcd(a,c)=1$ and $\gcd(b,d)=1$. Then is it true that,$$\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$$ I'm awfully weak in number theory. Can anyone please ...