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

learn more… | top users | synonyms

1
vote
1answer
24 views

Primes related to the structure $\left| \pm a\pm b\pm c \right| $

Let $(a,b,c)$ be any coprime positive integers such that $a+b+c\neq 2x$ where $x$ is any integer Let $${N_1,N_2,N_3,N_4}=\left| \pm a\pm b\pm c \right| $$ In most of the cases why is at least one of ...
1
vote
2answers
151 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
1
vote
1answer
47 views

Fractional part optimization algorithm

I was trying, out of curiosity, to find an efficient algorithm for the problem below which peaked my interest: Let $r$ be a real number. Find an integer $k > 0$ such that $kr$ is "near" an ...
1
vote
1answer
94 views

Euler totient function sum of divisors. Theorem 2.2 Apostol

Prove that : $If $ $ n\ge{1} $ $ \sum_{d|n}\phi(d)=N $ $ N \in{\mathbb Z} $ Let S denote the set {1,2,...,n}. We distribute the integers of S into disjoint sets as follows. For each divisor d ...
1
vote
2answers
77 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
1
vote
1answer
36 views

Smallest sample to produce n%

Q: A Statistic is published that 31% of people think it is okay to smoke in public. What is the smallest sample that could have been interviewed to get this result. A: 13, with 4 "yes" and 9 "no" ...
1
vote
1answer
42 views

On representing the general solution for the diophantine equation $a_1x_1+\dotsb+a_nx_n=c$

On representing the general solution with the special solutions for the diophantine equation $$a_1x_1+a_2x_2+\dotsb+a_nx_n=c$$ here $a_1 ,a_2, \dotsb,a_n,c\in\Bbb Z,(a_1 ,a_2, \dotsb,a_n)=1$. Can ...
1
vote
1answer
49 views

The Sum of Sets

I am looking up Niven http://projecteuclid.org/download/pdf_1/euclid.bams/1183516304 . I have something elementary to ask. Now, $A(n) $ denotes the number of integers of A which are not greater than ...
1
vote
2answers
68 views

Remainder of the polynomial

A polynomial function $f(x)$ with real coefficients leaves the remainder $15$ when divided by $x-3$, and the remainder $2x+1$ when divided by $(x-1)^2$. Then the remainder when $f(x)$ is divided by ...
1
vote
1answer
36 views

Problem with divisibility

Proof of the following without induction : $13| 3^{n+2} + 4^{2n+1}$ for every $n \in \mathbb{Z}^+$ Any help is apprciated.
1
vote
2answers
49 views

Diophantine word problem

A farmer purchased $100$ head of livestock for a total cost of $4000$. Prices were as follows: calves, $120$ each; lambs, $50$ each; piglets, $25$ each. If the farmer bought at least one animal of ...
1
vote
1answer
40 views

Complexity of primenumber test

The german wiki claims that the approach to check if any number before p is a divisor of p is a polynomial time algoritm. I dont understand this claim. Because imho this is linear, which is polynomial ...
1
vote
1answer
31 views

Show that λ(m)<Φ(m) for every odd composite number m.

I know that every odd composite number m factors into a set of odd primes. m=p1^(e1)p2^(e2)***pn^(en). I believe that in this situation λ(m)=[(p1-1)^(e1), (p2-1)^(e2), . . ., (pn-n)^(en)], but please ...
1
vote
1answer
103 views

The Cantor Set and Triadic Expansion

let $K$ be the Cantor set. I say that a number $x$ in $[0,1]$ is triadic if $x=\frac{m}{3^n}$ for some nonnegative integers $m, n$. Let $z$ be a triadic number in $[0,1]$. Do there exist two ...
1
vote
1answer
77 views

Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2

Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2. If p=2^k-1 is prime, show that k is an odd integer, except when k=2 Hint: 3|4^n-1 for all n>=1 ...
1
vote
2answers
67 views

Finding all solutions to $3^x \equiv 9 \pmod{13}$

Find all solutions to $3^x \equiv 9 \pmod{13}$. I don't know how to solve this problem. $3$ is a primitive root for $\mod{13}$ but the solution uses $2$ as a primitive root. Why can't I use $3$? ...
1
vote
1answer
58 views

prove perfect square

Show that if $ab$ and $bc$ are perfect squares then $ac$ is a perfect square using theorem of arithmetic. I am not exactly sure how to prove this. I know that a perfect square must have even powers of ...
1
vote
1answer
27 views

Totient function inequality

I am not quite sure how to approach this problem: If a and n are such natural numbers that a divides n, then $n-ϕ(n)\ge a-ϕ(a)$ This is my thought process so far: Obviously the fact that $n=n*a$ ...
1
vote
1answer
37 views

Number theory problem

Let $P(x) \in Z/pZ[x]$ be a polynomial of degree d. Prove that P(x) has d distinct roots in Z/pZ if and only P(x) divides $x^p-x$, namely, $x^p-x \equiv P(x)Q(x) \bmod p$ for some polynomial Q. ...
1
vote
1answer
32 views

$a,b\in\mathbb{N}$ and $ab>2$.Suppose,lcm$(a,b)=L,\gcd(a,b)=G$ and $a+b\mid L+G$.Prove that $\dfrac{(a+b)}{4}(a+b)\ge (L+G)$ and $a,b$ are two odd… [duplicate]

$a,b\in\mathbb{N}$ and $ab>2$.Suppose,$\text{lcm}(a,b)=L,\gcd(a,b)=G$ and $a+b\mid L+G$.Prove that $\dfrac{(a+b)}{4}\cdot(a+b)\ge (L+G)$. Also prove that equality occurs when $a,b$ are consecutive ...
1
vote
1answer
119 views

Linear Diophantine Equations

I was asked to find i) all integer solutions, and ii) all non-negative integer solutions to the equations below. I know (a) has no answers, but have no idea how to go about proving the rest. ...
1
vote
1answer
50 views

Help with proving bezout's theorem?

Let $a,b,c\in\mathbb Z$ where $d=\gcd(a,b)$ and $c$ is a multiple of $d$. Suppose that $(x=x_0, y=y_0)$ is one particular integer solution to $$ax+by=c.$$ Then the complete set of integer ...
1
vote
2answers
35 views

Euler's Theorem to solve for X

$x^{138} \bmod 77 = 25$. How can I use Euler's Theorem to solve for $x$. $77$ is not a prime number but its factors are. $7$ and $11$ are prime, so the totient function of $77$ will be $60$
1
vote
1answer
38 views

Divisibility problem with product of two primes

Be $n=pq$ a natural number product of two different primes $p,q$. Prove, that on the set $\{1.2,2.3,...,n(n+1)\}$ there are exactly 4 numbers divisible by $n$.
1
vote
4answers
89 views

Pre College Mathematics

During my school days I was a very keen student of mathematics. But circumstances led me to opt for commerce at the college level. Now I wish to continue learning mathematics on a self study basis. ...
1
vote
1answer
79 views

What is quadratic equations in Algebra?

Yesterday someone asked a question in SE about indeterminate quadratic equations(of the form $x^2−ny^2=1$ which got me really interested in them and I thought I would try to learn something related to ...
1
vote
1answer
41 views

Number theory problem - powers

Find the smallest prime $p$ such that for any $1 \leq k \leq 10$ relatively prime to $p$, one of $k, k^2,\ldots k^{p - 2}$ is congruent to $1$ modulo $p$. I am honestly not sure how to approach this ...
1
vote
1answer
33 views

Properties of the two ratios added

If $a,b,c,d$ are all positive integers with $\gcd(c,d)=1$ and $$\frac{1}{a}+\frac{1}{b}=\frac{c}{d},$$ what can I say about the relationship between the factors of $a$ and $b$? For example, if ...
1
vote
2answers
64 views

Prove that if d is a common divisor of a and b, then $d=\gcd(a,b)$ if and only if $\gcd(a/d,b/d)=1$

Prove that if d is a common divisor of a and b, then $d=\gcd(a,b)$ if and only if $\gcd(a/d,b/d)=1$ So far I used what was given so I have $a=dk$, $b=ld$ and $\gcd(a,b)=d$ can be written as a linear ...
1
vote
1answer
95 views

Does an expression exist such that…

Can you prove or disprove the existence of an expression P, such that $Z=6ab+a+b-P$ Makes Z expressible in the form; $Z=6xy\pm x \pm y$ for all a and b where $a,b,x,y∈N $ Finding an example of ...
1
vote
4answers
46 views

how do i prove $ab|n$ if $\gcd(a, b) = 1$ and $a|n $ and $b|n$?

Suppose that, for integers $a, b,$ and $n,$ $$\gcd(a, b) = 1\text{ and }a|n\text{ and }b|n.$$ How do I prove that $ab|n$ using linear Diophantine equations? Can I extend the above result to the ...
1
vote
1answer
88 views

Find the coefficients such that all four roots of $(x^2-px+q)(x^2-qx+p)$ are natural numbers

Find all ordered pairs $(p,q)$ of natural numbers such that all $4$ the roots of $$f(x)=(x^2-px+q)(x^2-qx+p)$$ are natural numbers. I got a solution of the problem (see below) but I want some ...
1
vote
1answer
43 views

finding least number

Question: The least number which when divided by 5, 6 , 7 and 8 leaves a remainder 3, but when divided by 9 leaves no remainder, is: solution: L.C.M. of 5, 6, 7, 8 = 840. Required number is ...
1
vote
1answer
30 views

Is $\sum_{j=1}^{k}a^j \equiv 0 \mod p\;$? where k is the order of $a \mod p$, with $p$ being an odd prime?

In other words is $a^1 + a^2 + \dotsm a^k \equiv 0\mod p\;$? This is true when $a$ is a primitive root of $p$ because $a^1, a^2, \dotsc a^k$ are congruent to $1,2,\dotsc,p-1$ in some order. Hence, ...
1
vote
2answers
28 views

A detail in this textbook's proof of the Chinese Remainder Theorem.

I have a question regarding a line in this proof: The system of congruences $x \equiv a_1 (\mod m_1)$ and $x \equiv a_2 (\mod m_2)$ where $(m_1, m_2) = 1$, has a unique solution modulo $m_1m_2$. ...
1
vote
1answer
60 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 ...
1
vote
3answers
115 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 ...
1
vote
1answer
66 views

Geometrical series with 9

You have this infinite sum: $\frac{1}{9} + \frac{1}{99} + \frac{1}{999} + \frac{1}{9999} + ...$ Take a truncated sum (just $n$ terms) and consider the numbers on the right side of the point. Which ...
1
vote
1answer
64 views

If $n\nmid a,a+d,a+2d. . . a+(n-1)d$,then $(n,d)=1$

None of the numbers in the sequence $a,a+d,a+2d,a+3d. . . a+(n-1)d$ are divisible by $n$.Then we have to prove that d and n are coprime. I am supposed to use the pigeonhole principle for this ...
1
vote
2answers
90 views

Proof: If $a\mid b$ and $b\mid c$, then $a\mid c$

Proof: If $a\mid b$ and $b\mid c$, then $a\mid c$ Can you tell me if my proof is correct?? If not what is wrong-step by step explanation please! $b/a = l$ ($l$ is an integer) $c/b = e$ ($e$ is an ...
1
vote
1answer
127 views

Gauss formulas to decompose a prime in the sum of two squares

I am looking for a demonstration of the formulas to decompose a prime $p\equiv 1$ $mod$ $4$ in the sum of two squares, cited in H. Davenport, The Higher Arithmetic. I have not found anything on the ...
1
vote
2answers
98 views

Quadratic residue of $-1$ in composite modulus

It is true for each odd prime number p that if $x^2\equiv-1 \pmod p$ then $p\equiv1\pmod 4$ I've observed that it should be true for all composite integers, whose prime factors are congruent to $1$ ...
1
vote
1answer
77 views

Eliminating numbers from the sequence $1,2,3,4,5,6,7…400$

BdMO 2014 Let us take the sequence $1,2,3,4,5,6,7....400$ .We are going to remove numbers from the sequence such that the sum of any 2 numbers of the remaining sequence is not divisible by 7.What ...
1
vote
1answer
114 views

Wilson's theorem and congruence

Establish that $x^2 \equiv −1 \pmod {pq}$ has no solutions if $p \equiv 3 \pmod 4$ or $q \equiv 3 \pmod 4$ Show that if $p$ is an odd prime such that $p \equiv 1 \pmod 4$, then $x^2 \equiv −1 \pmod ...
1
vote
1answer
55 views

Let $a_1,a_2,\ldots,a_{100}$ be real numbers,each less than one,satisfy $a_1+a_2+\ldots+a_{100} >1$.Prove the following statements

Let $a_1,a_2,\ldots,a_{100}$ be real numbers,each less than one,satisfy $$a_1+a_2+\ldots+a_{100}>1$$ Prove the following statements: (i) Let $n_0$ be the smallest integer $n$ such that ...
1
vote
1answer
25 views

Show that if $a\neq b$, $p^a \mid\mid M$ and $p^b \mid\mid N$, then $p^{\min\{a,b\}}\mid\mid M+N$.

Let $p^a \mid\mid N$ mean that $p^a$ is the largest power of $p$ that divides $N$. Show that if $a \neq b$, $p^a\mid\mid N$ and $p^b \mid\mid M$, then $p^{\min\{a+b\}}\mid\mid M+N$. Since $p^a ...
1
vote
2answers
71 views

Find number of triplets

How many triples of positive integers $(a,b,c)$ satisfy $a\le b\le c$ and $abc=1,000,000,000$ I tried prime factorizing R.H.S. and solving equivalently, the equation $\alpha$ + $\beta$ + ...
1
vote
1answer
48 views

Understanding the proof for $\gcd (F_n, F_{n+k}) = 1$ where $F_n$ is a Fermat number

I'm trying to understand the following proof of why No two Fermat numbers have a common divisor greater than $1$. Hardy and Wright show the following proofs: If $x = 2^{2^n}$, we have ...
1
vote
1answer
31 views

Converting Fibonacci number $F_{5n+3}$ to Lucas numbers $L_{n+k}$

I'm trying to prove that$F_{5n+3}\text{mod}10 = L_{n}\text{mod}10$. I rearranged it into a more solvable form of $F_{5n+3}-L_n = 10k$ (because if two numbers end in the same digit, their difference ...
1
vote
2answers
58 views

Complete System Residue problem

I have to proof that given a complete system residue modulo $k$ ( $k$ is prime ) { $a_1, a_2, a_3, \ldots a_k$ } that, for every integer $n$ there exists s such that: $n \equiv \sum\limits_{i=0}^s ...