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

learn more… | top users | synonyms (1)

0
votes
0answers
56 views

solution of the Pythagorean triple (a,b,21025)

I know that most intelligent people on this site will find this elementary question very simple (I hope you'll forgive me, I'm not yet familiar enough with mathematics): What is the solution of ...
0
votes
0answers
57 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are. Simply inserting f=0 contradicts the suggested number of solutions. Let $p$ be an odd ...
0
votes
0answers
26 views

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite?

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite? Is there a general way to determine the number of ...
0
votes
0answers
23 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
2
votes
1answer
34 views

If $p$ is an odd prime show that $2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$

If $p$ is an odd prime show that $$2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$$ This is an exercise from Elementary Number Theory, 2nd Edition by Underwood Dudley. I know that the expression ...
2
votes
2answers
63 views

Find triples $(a,b,c)$ of positive integers such that…

Find the triples $(a,b,c)$ of positive integers that satisfy $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)=3. $$ I found this on a local question paper, and I am ...
1
vote
1answer
19 views

Is a divides infinitely many repunits?

Let (a,10)=1 Let n=9k{phi(a)} using eulerphi function k is positive integer. When (a,9)= 1 , 3 it is okay Because 81 and a divides 10^n-1 by Binomial theorem and CRT So a divides (10^n-1)/9 ...
0
votes
0answers
12 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
2
votes
1answer
50 views

Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square.

Question: Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square. What I have attempted; For $x^2 + 13x + 3$ to be a perfect integer square let it equal ...
2
votes
1answer
32 views

If $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime, Then $p \equiv 29 (mod \; 30)$

Assume that $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime. Then I want to prove that $p \equiv 29 (mod \; 30).$ First of all I have to show that $4p+1$ is a ...
1
vote
1answer
43 views

Smallest positive integer r such that $8^{17} \equiv r \pmod {97}$

I want find out the Smallest positive integer r such that $8^{17} \equiv r \pmod{97}$. Fermat's theorem only tells us $8^{96} \equiv 1 \pmod{97}.$ How can I proceed. Any hint will be appreciated. ...
1
vote
0answers
13 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
2
votes
1answer
14 views

Boundedness of set with function on prime divisors

Let $P(n)$ denote the product of the prime divisors of $n$, e.g., $P(100)=2\times 5=10$. Define $$A=\{\frac{a}{P(ab(a-b))} \mid a,b\in\mathbb{Z}^+, a>b\}.$$ Is $A$ bounded or not? To make the ...
1
vote
2answers
78 views

A prime number problem.

If $n$ is a positive integer and $(p_1,p_2,p_3,p_4,\ldots, p_n)$ are distinct positive primes, show that the integer $(p_1\cdot p_2\cdot p_3\cdot p_4\cdots p_n)+1$ is divisible by none of these ...
1
vote
1answer
17 views

Reference for table of cubes modulo $m$?

Is there an online table with all the cubes in $(\mathbb{Z}/m\mathbb{Z})$ (with $m$ up to (say) $100$, at least)? I didn't find anything googling it. Thanks.
0
votes
0answers
12 views

Which of a,b,c,d is/are odd given the set of conditions?

I am trying to answer this question. Which of a,b,c,d is/are odd given the set of conditions? Condition 1.) ad + bc is odd Condition 2.) ac + bd is odd The question is actually asking if we can ...
0
votes
1answer
23 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n ...
3
votes
2answers
56 views

if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property : $$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$ Knowing that : Definition Given two ...
-2
votes
0answers
15 views

Understanding Primitve Root and Congruences relation. [closed]

Please help me understand following proof in very elementary way you can.
2
votes
1answer
39 views

Find all $n$ such that $n|1^n + 2^n + 3^n + \cdots + (n-1)^n$ where $n \in \mathbb{Z}^+$.

Find all $n$ such that $$n|1^n + 2^n + 3^n + \cdots + (n-1)^n$$ where $n \in \mathbb{Z}^+$. I don't know how to start. $n = 3, 5$ are simple solutions. Induction seems strange since the divisor ...
0
votes
1answer
20 views

$n-1 = pq-1 \equiv q-1\pmod{p-1}$ where $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$.

Let $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$. My lecturer simply states that $$n-1 = pq-1 \equiv q-1\pmod{p-1}$$ without any justification and I can't see how this ...
-2
votes
0answers
30 views

The prime divisors of $N= 3^{1000}.2^{2000009}+1$ are congruent to 1 modulo $2^{2000009}$

Let $N= 3^{1000}\cdot 2^{2000009}+1$. Assume that $5^{\frac{N-1}{2}} \equiv -1 \pmod N$. Let $p$ be a factor of $N$. Then my questions are the following: Which power of $2$ divides ...
0
votes
0answers
32 views

$\Bbb N \times \Bbb N$ is countable induction

I was trying to to prove $\Bbb N \times \Bbb N$ is countable, If I let $f:\Bbb N \times \Bbb N \to \Bbb N$ be given by $f((m,n))= m+\sum_{i=0}^{m+n-2}i$ then $f(1,1) = 1\\ f(1,2) = 2\\ ...
0
votes
1answer
22 views

Sum of primes less than or equal to K is greater than K

I am trying to show that the sum of primes less than or equal to some $k \in \mathbb{N}$ must be greater than $k$ itself. My hint was to use Bertrands Postulate but I am not getting anywhere.
0
votes
0answers
15 views

Using the fact that 6 is a primitive root modulo 109, compute the remainder when 424^2076 divided by 109

Using the fact that 6 is a primitive root modulo 109, compute the remainder when $424^{2076}$ is divided by 109. I try with ord_109 (6)=phi(109) =108 424 = 97mod 109 stuck here
0
votes
1answer
42 views

Understanding a proof of a corollary in chapter 2 about invertibility of a p-adic integer (Jean-Pierre Serre)

In a proof of a corollary in chapter 2, there is a step I don't understand. Corollary 2: Suppose $p \neq 2$. Let $f(X) = \sum_j a_{ij}X_iX_j$ with $a_{ij} = a_{ji}$ be a quadratic form with ...
0
votes
3answers
69 views

Determine: $13^{-1} \pmod {67}$

Determine: $13^{-1} \pmod {67}$ I'm not sure how to deal with the negative one here as it inverts the integer? Any help would be appreciated!
0
votes
0answers
24 views

Difference between a quadratic residue and a number is a quadratic residue

Let $p$ be an odd prime, and let $a\in\mathbb{Z}_p^*$, i.e. $a\not\equiv 0$. Let $q_1,\ldots,q_{\frac{p-1}{2}}$ be the quadratic residues mod $p$. Is there a way of knowing how many $j\leq ...
2
votes
1answer
53 views

Determining a multiple of a power of 2.

I am thinking about this question which I believe is a possible GRE question. "Which of the following numbers is exactly divisible by 32? A) $1.9 \times 10^5 $ B) $1.9 \times 10^6$ C) $1.9 \times ...
1
vote
1answer
55 views

a question about rational power irrational is irrational?

Please help me about the following question. Prove $2^e$ is an irrational number where $e$ is Neipper number. Thanks
2
votes
2answers
47 views

Prove that if $\gcd(a,b)=1$ and $a|mb$ then $a|m$. [duplicate]

I've tried out a few pairs of numbers for $a$,$b$ where I have combinations of prime-prime, prime-non prime, non-prime-non-prime, and I know the statement is true, but how should I go about proving ...
2
votes
2answers
57 views

$7^{6} | (a+b+ab)^2$ Find the value of $a,b$ [closed]

$7^{6} | (a+b+ab)^2$ Find the value of a,b. I have used trial and error for a singular solution. But a generalized solution will be helpful. Provide me the concept to deal with this problem and ...
7
votes
0answers
83 views

Does anyone know a reference to best-fitting lines with integral coefficients?

I'm writing up a manual on how to generate "nice" Linear Algebra problems; that is, where the solutions tend to be integral. I "discovered" the following fact about the best-fitting line: Theorem. ...
1
vote
3answers
50 views

If $p$ and $q$ are positive prime numbers such that $p$ is divisible by $q$, show that $p = q$.

To solve this problem, this is my approach. Assume $p\mid q$, there exists an $n∈N$ and assume $q\mid p$, there exists an $m∈N$. This would mean that $p=qn$ and $q=pm$. Then using substitution, ...
0
votes
1answer
28 views

Let $5 \leq k < n$. Then $2k$ divides $n(n - 1)… (n - k + 1)$. What should I use permutations or polynomials?

Let $5 \leq k <n$. Then $2k$ divides $n(n-1)\cdots(n-k + 1)$. Is it true? Please provide a proof. I am confused about using induction, polynomial properties or permutations to solve this problem.
1
vote
1answer
28 views

The prime counting function has a lower bound of $C\log\log x$

I read that using Euclid's Theorem and by induction, a "gross underestimation" of the Prime Counting Function $\pi(x)$ can be stated as $C \log \log X$, i.e there is a constant $C$ such that the ...
3
votes
0answers
46 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
0
votes
1answer
16 views

Find elements of a set that divide an expression.

I have to determine the elements of the following set: $A = \{x\in\ \mathbb Z \vert \sqrt[3]{\frac {7x + 2}{x+5}} \in \mathbb Z \}$ I know that $x+5 \not=0$ and $x+5$ must divide $7x + 2$ but I ...
2
votes
0answers
17 views

If $a\not\equiv 0\mod{p}$ then there are $p-1$ solutions (ordered pairs) to $x^2-y^2\equiv a\mod{p}$

Let $p$ be an odd prime, and let $a\in\mathbb{Z}_p$ such that $a\not\equiv 0$. I need to show that there are $p-1$ ordered pairs $(x,y)$ such that $x^2-y^2\equiv a \mod{p}$. As I see it, the ...
0
votes
1answer
33 views

How many people are in the room?

The ratio of men to women is $3:4$, the ratio of Americans to non-Americans is $7:2$, and the number of people that are in the room is less than $100$. How many people are in the room? I am helping ...
6
votes
1answer
40 views

Can I apply Chinese remainder theorem here?

A number when divided by a divisor leaves $27$ remainder. Twice the number when divided by the same divisor leaves a remainder $3$. Find the divisor. My attempt: Let, the number be=$n$ and the ...
1
vote
2answers
16 views

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. ...
0
votes
1answer
25 views

Simple question about divisibility and modular arithmetic

Is the following true? Fix an $n\in \Bbb N$ which is not a multiple of $5$. Then for every $l\in\{0,\cdots,n\}$ there exists a $k\in \Bbb N_0$ with $5k\equiv l \mod n$. If yes, how do we prove it?
3
votes
1answer
31 views

$\frac {2 \cdot 3^{m + 1}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \in \Bbb N_+$, find all possible values of $k, m$.

If $$\frac {2 \cdot 3^{m + 1}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \in \Bbb N_+$$ and $$\frac {2 \cdot 3^{m}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \le 1$$ where $k, m \in \Bbb N_+$ and $k \ge 2$, find all ...
1
vote
0answers
19 views

Transformations between Pell[-like] equations

I’m looking for [non-trivial] transformations that take a Pell-like equation $$ u^2-dv^2=w $$ and turn it into another Pell-like equation $$ x^2-my^2 = z. $$ Best-case scenario, one could always use ...
-2
votes
1answer
43 views

Show that if $x = y + z$ , and $d$ is a divisor of any two of the integers $x$, $y$, and $z$, it is also a divisor of the third. [closed]

Show that if $x = y + z$ , and $d$ is a divisor of any two of the integers $x$, $y$, and $z$, it is also a divisor of the third. How should I approach this problem and using what method to solve ...
2
votes
1answer
51 views

Every subset of a finite set is finite

Is there anyway I can prove this statement using the pigeonhole principle below? "If A,B are sets and B is finite, and there is an injection $f : A \rightarrow B$, then A is finite and $Card(A)\leq ...
0
votes
2answers
55 views

Determine $x$ if $x = 4 \mod 17$ and $x = 3 \mod 11$. [closed]

Given $x =4\mod 17$ and $x = 3\mod 11$, determine $x$. I know that $\gcd(17,11)= 1$. I was hoping to use this to determine $x$.
1
vote
2answers
25 views

Find all prime p such that Legendre symbol of $\left(\frac{10}{p}\right)$ =1

In the given question I have been able to break down $\left(\frac{10}{p}\right)$= $\left(\frac{5}{p}\right)$ $\left(\frac{2}{p}\right)$. But what needs to be done further to obtain the answer.
0
votes
2answers
45 views

Prove that for every integer $n$ there exists a unique integer $m$ such that $2m + 8n = 6$.

Prove that for every integer $n$ there exists a unique integer $m$ such that $2m + 8n = 6$. My method: Let $n$ be given. We know that $2m + 8n = 6$. Then $2m = 6 - 8n$. Thus, $m = 3 - 4n$. I am ...