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

learn more… | top users | synonyms (1)

7
votes
3answers
307 views

Proving there are no integers $a, b, c$ satisfying $12a + 18b + 27c = 227$

Given $12a + 18b + 27c = 227$, how can we prove that $a, b, c$ can never be integers? I don't have many ideas. Can someone give me some ideas?
2
votes
6answers
237 views

Proving that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$

Prove that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$. I know that for proving the $\gcd(a,b) = c$ you need to prove $c|a$ and $c|b$ $c$ is the greatest number that divides $a$ and $b$ Number 2 ...
2
votes
1answer
268 views

For what primes $p$ does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically?

this is a question from a book I'm struggling with, please could you provide a clear proof For what primes p does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically? kind thanks
1
vote
2answers
193 views

Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$.

This is a question from a book I'm struggling with, please could you provide a clear proof? Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$. kind thanks
0
votes
1answer
73 views

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically and, when it does, to what limit?
0
votes
2answers
98 views

$\operatorname{lcm}(\operatorname{gcd}(a,b),c)=\operatorname{gcd}(\operatorname{lcm}(a,c),\operatorname{lcm}(b,c))$ for any $a,b,c \in \mathbb{Z}$

I tried to show that the lattice of subgroups of the group $\mathbb{Z}$ is distributive. The question reduced showing that for any $a,b,c \in \mathbb{Z}$ we have that $$ ...
2
votes
2answers
199 views

Which integers can be expressed as a sum of squares of two coprime integers?

I want to find integers $z=a^2+b^2$ with $\gcd(a,b)=1$. Clearly all prime numbers of the form $4k+1$ are such numbers, but what other composite numbers also enjoy this property? e.g. $74=5^2+7^2$, ...
0
votes
2answers
682 views

Proof by induction that $n^3 - n$ is divisible by $6$

Show using induction that $n^3-n$ is divisible by 6 $\forall n\ge1, \quad n \in \mathbb{N}$ First off i show that the basis step: $1^3-1=0, \quad \frac{0}{6}=0$ Now I factorised it and set it ...
3
votes
4answers
2k views

Proof by induction; $a^n$ divides $b^n$ implies $a$ divides $b$

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$. clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$. Suppose this is true ...
3
votes
2answers
182 views

Proving there is a primitive root mod $p$ such that $a^{p-1} \not\equiv 1 \pmod{p^2}$

Prove there is a primitive root mod $p$ such that $a^{p-1} \not\equiv 1 \pmod{p^2}$. ($p$ is an odd prime.) I don't know how to start this question.
1
vote
5answers
1k views

Solutions of the congruence $x^2 \equiv 1 \pmod{m}$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$. Thanks.
3
votes
9answers
1k views

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$. I believe this might be tried using division algorithm, or modular arithmetic. I don't see exactly how to start this... Please help.
1
vote
2answers
224 views

Creating the set of natural numbers

I am not a mathematician but an engineer, so I can read some basics of the language proofs are written in. Second I am bad in probability and infinity and my question covers both. So I like to ...
0
votes
1answer
90 views

Proving there is an $a$ that is not a quadratic residue mod $p$ for any prime $2 < p \leq 1000$

Prove there is an integer $a$ such that for all primes $p$ between $2$ and $1000$, the number $a$ is not a quadratic residue mod $p$. Thanks.
2
votes
2answers
77 views

Determining if there is a solution to $2004x^2+2005y=1$ for integers $x,y$

I have an equation and need to decide if there is a solution to $$2004x^2+2005y=1,$$ where $x$ and $y$ are integers. A clue: $2005=5\cdot401$ and $401$ is a prime number. How to start question like ...
4
votes
2answers
176 views

Can twice a perfect square be divisible by $q^{\frac{q+1}{2}} + 1$, where $q$ is a prime with $q \equiv 1 \pmod 4$?

Can twice a perfect square be divisible by $$q^{\frac{q+1}{2}} + 1,$$ where $q$ is a prime with $q \equiv 1 \pmod 4$?
0
votes
2answers
150 views

Quicker Way to Compute Modulus?

Are there any tricks associated with finding a large value $mod$ another value? I'm working on problems that involve computing the Legendre symbol value and need to take the modulus of another prime ...
0
votes
3answers
269 views

Finding the remainder after dividing $2^{2^{17}} + 1$ by $19$

Can you please give me any hints for finding the modulo of the division of $\large \displaystyle 2^{2^{17}} + 1$ with the number $19$. Thank you.
0
votes
3answers
98 views

Find the solutions of system of equivalences for modulo

Can you please help me solve the system of equivalences: $x \equiv 3 \pmod {13}$ and $x \equiv 3 \pmod {17}$ and $x \equiv 13 \pmod {23}$ Thank you!
2
votes
5answers
287 views

Finding solutions of the system $27x + 90 \equiv 18 \pmod{99}$

I have to find solutions for the expression $$27x + 90 \equiv 18 \pmod{99}$$ My only problem is that I can only solve expressions like $ax \equiv b \pmod{n}$. How can I get rid of the $90$? ...
4
votes
4answers
121 views

Proving $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$

We suppose $\forall n \in \mathbb {N}\setminus{0}$. How can I prove that $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$?
2
votes
2answers
383 views

Finding all quadratic residues

$p$ is an odd prime. $a$ is a primitive root mod $p$. Prove that the quadratic residues mod $p$ are $a^{2i}$ when $0 \leq i \leq (p-1)/2$. What I know is that $a^{2i}$ are always quadratic ...
2
votes
3answers
73 views

Showing that $3^{(p+1)/4}$ satisfies $x^2 \equiv 3 \mod p$ for primes $p\equiv11 \mod 12$

Let $p$ a prime with $p\equiv11 \mod 12$. I have to prove that $3^{(p+1)/4}$ is a solution to $x^2\equiv3\mod p$. This is how I start: There is a solution because $p\equiv11 \mod 12 \Rightarrow ...
9
votes
4answers
10k views

How do the floor and ceiling functions work on negative numbers?

It's clear to me how these functions work on positive real numbers: you round up or down accordingly. But if you have to round a negative real number: to take $\,-0.8\,$ to $\,-1,\,$ then do you take ...
7
votes
5answers
182 views

Find remainder of $F_n$ when divided by $5$

Let $\{ F_n\}$ be the sequence of numbers defined by $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$ for $n \geq 2$. Let $f_n$ be the remainder left when $F_n$ is divided by $5$. Then $f_{2000}$ equals ...
1
vote
5answers
198 views

To prove a property of greatest common divisor

Suppose integer $d$ is the greatest common divisor of integer $a$ and $b$, how to prove, there exist whole number $r$ and $s$, so that $$d = r \cdot a + s \cdot b $$ ? i know a proof in abstract ...
0
votes
4answers
108 views

Number of distinct prime divisors given $\phi(n)$

Suppose that $a = 2^kb,$ where $b$ is odd. If $\phi(x) = a,$ prove that $x$ has at most $k$ odd prime divisors.
1
vote
1answer
445 views

Finding All Integers in such that $\phi(n)=80$

I don't know where to start with this problem so please help. The problem is: Find all integers n such that $\phi(n) = 80$.
1
vote
1answer
87 views

Erdős–Turan construction of Golomb ruler

The following equation produces a Golomb ruler for every odd prime p $$ 2pk + (k^2 \bmod p), \quad k\in[0,p-1] $$ and every two contiguous points has a unique difference. my question is how to get ...
3
votes
1answer
70 views

Computing the period of a fraction polynomial in the number of digits

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
2
votes
1answer
435 views

Proof involving Legendre Symbol

I’m having a really difficult time with the following proof involving the Legendre symbol: Show that $\left(\dfrac{3}{p}\right) = 1$ iff $p \equiv \pm 1 \pmod{12}$ The normal tricks don’t seem ...
5
votes
1answer
248 views

Prove ${a^2+ac-c^2=b^2+bd-d^2}$ and $a > b > c > d \implies ab + cd$ is not prime

Let $a>b>c>d$ be positive integers and suppose that $${a^2+ac-c^2=b^2+bd-d^2}$$ Prove that $ab+cd$ is not prime? I don't know if this problem is true. I found that this same problem has ...
3
votes
1answer
58 views

Definition of quadratic residue

According to Wikipedia, $q$ is a quadratic residue $\mod n$ if there exists an integer $x$ such that $x^2 \equiv q \mod n$. Some other sources add the assumption that $q$ and $n$ are coprime. Which ...
4
votes
1answer
661 views

Computing the Legendre symbol $\bigl(\frac{3}{p}\bigr)$ using Gauss' Lemma

I would like to compute the Legendre symbol $\bigl(\frac{3}{p}\bigr)$, where $p > 3$ is a prime using Gauss' Lemma. What I got so far is that $p$ can belong the following residue classes $\mod ...
0
votes
4answers
101 views

Polynomial division in $\mathbb{Z}_n[x]$

For which value of $n$ is $x^3-x$ divisible by $2x-1$ modulo $n$?
0
votes
1answer
647 views

Legendre Symbol Sum?

I’m attempting to prove the following: If $p$ is an odd prime and $a$ is a positive integer such that $p \space \nmid \space a$ then the following expression holds: $$(\frac{a}{p}) + (\frac{2a}{p}) ...
5
votes
5answers
143 views

Proving $n+3 \mid 3n^3-11n+48$

I'm really stuck while I'm trying to prove this statement: $\forall n \in \mathbb{N},\quad (n+3) \mid (3n^3-11n+48)$. I couldn't even how to start.
2
votes
5answers
74 views

Does $x^2 \equiv 0 \mod p$ have a solution other than $x = 0$?

I think it doesn't since if it did, by Euclid's lemma $p$ divides $x \in \{1,\dots, p-1\}$. Is this correct?
0
votes
2answers
55 views

Proving two Complexes' Numbers Properties

I'm having problem working with complex number on this question and was wondering if someone can walk through with me their reasoning on how to solve this/these types of questions. Thanks in advance! ...
2
votes
2answers
35 views

Prove that if $\gcd(a, n) = d$ then $\langle[a]\rangle = \langle[d]\rangle$ in $\mathbb Z_n$?

I am not sure how to start this problem and hope someone can help me out.
0
votes
5answers
311 views

For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I'm trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I'm having problems with the second. Here is ...
1
vote
2answers
50 views

Mersenne numbers congruent to two

Prove that $2^{2^n-1} = 2 \pmod{2^n - 1}$ given that $2^n = 2 \pmod n$. How would I go about proving that? I started by saying let $m = 2^n - 1$ Then, $2^n = 1 \pmod{m}$. So I need to prove $2^m = 1 ...
4
votes
2answers
368 views

Positive integer $2\times 2$ matrix with two positive integer square root matrices

So suppose I have this matrix: $$M=\begin{pmatrix}a & b \\ c & d \end{pmatrix}$$ I am sure that every entry is a positive integer. I am trying to figure out if it has 2 square roots in which ...
2
votes
3answers
157 views

Why does base $b$ have digits from $0$ to $b-1$?

Base system with $b \in \mathbb N$ consists of $b$ digits $d_0,d_1,d_2\dots d_{b-1}$. A number $a$ is expressed by some weighted sum of (integer) powers of $b$, where the digits $d_0,d_1,d_2\dots ...
0
votes
2answers
79 views

How to find the remainder $x^y\bmod z$ quickly?

I am searching for any rule to find the remainder $x^y\bmod z$ where $x,y,z$ are positive integer. Is there any rule to quickly find this remainder (without computing $x^y$)?
4
votes
4answers
1k views

Number system - sum of two digit numbers

The sum of four two digit numbers is $221$. None of the eight digits is 0 and none of them are same. Which of the following is not included among the eight digit ? $$(a) \;\;1 \\ (b)\;\; 2 \\ ...
1
vote
2answers
75 views

How to solve $5^{2x}-3\cdot2^{2y}+5^x\cdot2^{y-1}-2^{y-1}-2\cdot5^x+1=0$ in $\mathbb{Z}$

how to solve in $\Bbb Z$: $$5^{2x}-3\cdot2^{2y}+5^x\cdot2^{y-1}-2^{y-1}-2\cdot5^x+1=0$$
6
votes
1answer
86 views

$ g(n)= \sum_{d|n}\frac{\phi(d)}d=?$

how to find: $$f(n)=\sum_{d|n} d \phi(d)=? $$, $$ g(n)= \sum_{d|n}\frac{\phi(d)}d=?$$
5
votes
16answers
4k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
4
votes
2answers
623 views

How can I prove these summations for the legendre symbol

How can I prove for the Legendre symbol that: $$\sum_{a=1}^{p-1}{\left(\frac{a(a+1)}{p}\right)}= -1 = \sum_{b=1}^{p-1}{\left(\frac{(1+b)}{p}\right)}$$