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

learn more… | top users | synonyms (1)

1
vote
1answer
357 views

Disprove the statement “every positive integer is the sum of cubes of 8 non negative integers”

Disprove the statement "every positive integer is the sum of cubes of 8 non negative integers" May I know how can I disprove it. As far as concern, 0, 1, 2, 3... is can be obtained using the cubes ...
3
votes
3answers
68 views

For all $m\ge 2$, the last digit of $ 2^{2^m} $ is 6

How to prove that for $ \forall m\in \Bbb N $ such that $m\ge 2$, the last digit of $ 2^{2^m} $ is 6?
5
votes
5answers
104 views

$2005|(a^3+b^3) , 2005|(a^4+b^4 ) \implies2005|a^5+b^5$

How can I show that if $$2005|a^3+b^3 , 2005|a^4+b^4$$ then $$2005|a^5+b^5$$ I'm trying to solve them from $a^{2k+1} + b^{2k+1}=...$ but I'm not getting anywhere. Can you please point in me the ...
1
vote
4answers
103 views

Finding the remainder.

Let $a,b$ be positive integers such that $7$ divide $a^2+b^2$ .How to find the remainder when we divide $ab-1$ by $7$
2
votes
2answers
190 views

number theory - approximate square root of a prime number

Some prime numbers can be written in this form-- $$p \cdot a^2 =b^2 \pm 1,$$ where $p$ is a prime number and $a$ and $b$ are integers. for example :- $3=2^2-1$; $5=2^2+1$; $7 \cdot 3^2 = 8^2 -1$ ; $11 ...
0
votes
6answers
143 views

How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $?

How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $? Please give me some ideas. Thank you.
6
votes
3answers
318 views

Calculate $1\times 3\times 5\times \cdots \times 2013$ last three digits.

Calculate $1\times 3\times 5\times \cdots \times 2013$ last three digits.
2
votes
5answers
128 views

$x^2\mid27 \implies x\mid9$ : Prove

$x$ is given as a natural number. I was trying this by direct proof: assume $27\mid x^2$, then $x^2 = 27m \Longrightarrow x=3\cdot \sqrt{3m} \Longrightarrow \sqrt{3m}$ must be integer ...
1
vote
2answers
200 views

Uncertainty of process used in simple proof that there exists no rational number whose square is 2.

Hardy goes on by saying that suppose $\frac {p^2}{q^2}=\frac mn,$ where $p$ has no factor in common with $q,$ and $m$ no factor in common with $n.$ Then $n{p^2}=mq^2$. Here is where I get confused. ...
4
votes
1answer
189 views

Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
0
votes
1answer
304 views

If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one

I came across this Theorem in "Elementary Number theorem" by David B. Burton : "If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one." I am not able to understand why this result ...
3
votes
2answers
3k views

Using the Euler totient function for a large number

So I have a test in a couple of hours and I'm having trouble finding information on how to use the Euler totient function for a large number so I'm wondering if someone could give me step-by-step ...
1
vote
3answers
499 views

If the sum of the digits of $n$ are divisible by 9, then $n$ is divisible by 9; help understanding part of a proof [duplicate]

Let $n$ be a positive integer such that $n<1000$. If the sum of the digits of $n$ is divisible by 9, then $n$ is divisible by 9. I got up to here: $$100a + 10b + c = n$$ $$a+b+c = 9k,\quad ...
2
votes
1answer
172 views

Don't understand casting out nines

Let n be a positive integer. If the sum of the digits of n is divisible by 9, then n is divisible by 9. I got upto here, ...
3
votes
3answers
155 views

Solve $x^{11}+x^8+5\equiv 0\pmod{49}$

Solve $x^{11}+x^8+5\pmod{49}$ My work $f(x)=x^{11}+x^8+5$ consider the polynomial congruence $f(x) \equiv 0 \pmod {49}$ Prime factorization of $49 = 7^2$ we have $f(x) \equiv 0 \mod 7^2$ Test ...
3
votes
1answer
2k views

How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$

I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
-1
votes
1answer
94 views

$10\times10$ table of numbers with differences of adjacent entries no more than 5

In each square in a table $10\times 10$ we write a whole number so the difference between any two numbers by the neighboring squares must be no more than $5$ (two squares are neighboring if they have ...
1
vote
3answers
95 views

How could I go about solving $y^{20} \equiv 13 \pmod {17}$

How could I go about solving $y^{20} \equiv 13 \pmod {17}$ I know that phi(17) = 16. and gcd(20,16) = 4 ; 13^{16/4} ≡ 1 mod 17 So we must have 4 solutions. I am just learning about orders so I am ...
0
votes
1answer
74 views

If $k$ is any natural number, then does there exist a sequence $(p_n)$ of primes such that for each $n \in \mathbb{N}$, $k|(p_n +1)$?

If $k$ is any natural number, then does there exist a sequence $(p_n)$ of primes such that for each $n \in \mathbb{N}$, $k|(p_n +1)$? It would be equally good if one can prove/disprove the above ...
0
votes
2answers
145 views

The sum of odd numbers

How to know the sum of odd numbers that between $1$ and $1000$ and their remainder when we divide them by $5$ is $3$.
3
votes
3answers
77 views

Finding $x+y$ given that $(2^{28}-1)$ is divisible by $x,y$ and between $120 ,130$

The number $(2^{28}-1)$ is divisible by $x,y$.If each of $x,y$ is between $120 ,130$ .How to find $x+y$
4
votes
1answer
105 views

Prove: $n \in \mathbb{Z} \implies 4 \nmid (n^2-3)$

I'm trying to write a contrapositive proof. What I have seems somewhat legit, but it uses proof by contradiction couched within a contrapositive proof. Since this problem is presented before the ...
0
votes
2answers
207 views

What can we say about $\gcd(a,b)$ if $as + bt = 2$ fo rsome $s,t \in \mathbb{Z}$?

I have a question I can not figure out (It's #2 in section 4.4 of the book Discrete and Combinatorial Mathematics, by Ralph P. Grimaldi). $\mathbb{Z}^+$ = The set of all positive integers ...
5
votes
4answers
249 views

the unit digit for $3^{100}\cdot 37^{98}$

What is the best way to know the unit digit for $3^{100}\cdot 37^{98}$
6
votes
1answer
454 views

Rational points on a circle

A circle is centred at $(\pi,e)$. What is the maximum no. of rational points it can have? (A rational point is one with both coordinates rational). 1 rational point is definitely possible, just choose ...
2
votes
2answers
184 views

Proving solutions exist in a system of linear congruences

Suppose we have integers $a, b$, and $p$ where $p$ is prime. We also have naturals $n$ and $m$, where $n < m$. Prove that the system of linear congruences: $$x \equiv a \pmod{p^n}$$ ...
1
vote
1answer
330 views

How many permutations are there from x bits to y bits?

Can you have a permutation function where the size of the domain isn't the size of the range? I know the number of permutations from x bits to x bits is $2^x!$, but if you can permute x bits to y ...
6
votes
5answers
415 views

Continued Fraction [1,1,1,…]

If the continued fractional representation of an irrational number $\alpha$ is given by [1,1,1,...], I can compute that $\alpha = \frac{1+\sqrt{5}}{2}$ by solving the equation $\alpha = 1+ ...
2
votes
2answers
278 views

James has 773500 gold coins to purchase a number of hats and ties…

I have trouble with this one question. Much thanks for the answer! James has 773500 gold coins to purchase a number of hats and ties. Each hat costs 299 gold coins, and each tie costs 208 gold coins. ...
3
votes
3answers
110 views

Suppose $n$ is a natural number and $2^n-1$ is prime. Prove that $2^{n-1}(2^n-1)$ is perfect.

This is a question that has been bothering me for a while. If anybody can help me solve this, it would take a great burden off my chest. Thank you very much! Suppose $n$ is a natural number and ...
2
votes
2answers
487 views

Show that $n!+1$ has a prime factor $\;>n$; show $\exists$ infinite number of primes

I don't know how to prove this and it's really bugging me. Thanks to anybody that can help! Let $n$ be any natural number. Prove that $n! + 1$ contains a prime factor greater than $n$ and use that to ...
0
votes
1answer
80 views

Divisibility problem, number theory

Is $10^{is}-1$ divisible by $10^{s}-1$ there i, s are natural numbers. If so, how do I prove it? Thanks for help, I've delt with it. How I should go about proving this a bit harder divisibility ...
0
votes
6answers
174 views

If $x$ and $y$ are odd, prime integers, then $xy+x+y$ is not necessarily a prime number?

Prove the theorems: 1) If $x$ and $y$ are odd, prime integers, then $xy+x+y$ is not necessarily a prime number. 2) If $x$ is a positive odd integer, then $x^4$ can be written in the form $8m+1$ ...
1
vote
1answer
40 views

How to solve $2^{(x+1)^2}$ modulo $m$ (not prime) where $(x+1)^2$ overflows?

As stated in the question, I am trying to write a generic solver for $2^{(x+1)^2}$ modulo $m$ where $m$ is not prime. Normally you can just do exponentiated squaring with modulus to get the answer, ...
1
vote
1answer
532 views

Gödel, Escher, Bach: $ b $ is a power of $ 10 $.

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
6
votes
2answers
423 views

Let $p$ be an odd prime number. How many $p$-element subsets of $\{1,2,3,4, \ldots, 2p\}$ have sums divisible by $p$?

Since there are $2p$ elements in the set, there are exactly $p$ distinct remainders (including $0$) when divided by $p$. We can write it as : $1$ and $p+1 \equiv 1 \pmod{p}$ $2$ and $p+2 \equiv 2 ...
2
votes
2answers
474 views

Show that $\sigma(n) = \sum_{d|n} \phi(n) d(\frac{n}{d})$

This is a homework question and I am to show that $$\sigma(n) = \sum_{d|n} \phi(n) d\left(\frac{n}{d}\right)$$ where $\sigma(n) = \sum_{d|n}d$, $d(n) = \sum_{d|n} 1 $ and $\phi$ is the Euler Phi ...
2
votes
1answer
114 views

Euclids Algorithm Proof

Let $a,b$ be an element in $\mathbb{Z}$ with $a \ge b \ge 0$, let $d := \gcd(a,b)$ and assume $d \gt 0$. Suppose that on input $a,b$, Eculid's algorithm performs lambda division steps, and computes ...
3
votes
1answer
113 views

Number of roots for quadratic residues

Let $n \in Z$ and define $QR_n=\{x \in Z_n|\exists y \in Z_n :y^2=x (mod\ n)\}$. How can I show that $\forall x \in QR_n$ it hold that $|\{ y \in Z_n:y^2=x (mod\ n)\}|=\frac{n}{|QR_n|}$ ? Why am I ...
3
votes
2answers
219 views

Number base conversion

How can I convert a number from one base, $b_1 \neq 10$ to another base $b_2 \neq 10$ without going through base $10$ i.e. $b_1\rightarrow 10 \rightarrow b_2$?
5
votes
3answers
251 views

divisibility problem using induction

If $S_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$ show that $S_n$ is integer and that $S_{n+1}=6S_n-4S_{n-1}$. Further deduce that the next integer greater than $(3+\sqrt{5})^n$ is divisible by $2^n$. My work ...
0
votes
6answers
176 views

Exercise of divisibility of integer numbers

How to prove that if $a$ an $b$ are integers so that $3|(a^2+b^2)$, then $3|ab$?
14
votes
2answers
364 views

A question about integers.

Let $a,b,c$ be positive integer,and $\cfrac{a}{b}+\cfrac{b}{c}+\cfrac{c}{a}$ and $\cfrac{b}{a}+\cfrac{c}{b}+\cfrac{a}{c}$ are integers, how to show $a=b=c$?
4
votes
3answers
131 views

prove , if $p,q$ be two primes with the property , $q$=$p$+1 then $p$=2 and $q$=3

prove , if $p,q$ are two primes with the property , $q$=$p$+1 then $p$=2 and $q$=3 how can we prove something like that ? my information in number theory is not big , and i have no idea about the ...
2
votes
2answers
241 views

Prove that $a^{2^n}=1 \mod 2^{n+2}$

I would like to prove that $$a^{2^n}\equiv 1 \pmod {2^{n+2}}$$ I tried induction but could not get it. Thank you very much!
1
vote
2answers
77 views

Is Wiki wrong on Dirichlet Chararcters Modulo $10$?

Wiki says: Modulus 10 There are $\phi(10)=4$ characters modulo $10$. Note that $χ$ is wholly determined by $\chi(3)$, since $3$ generates the group of units modulo $10$. I can ...
3
votes
3answers
174 views

Prove that either $m$ divides $n$ or $n$ divides $m$ given that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$?

We are given that $m$ and $n$ are positive integers such that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$. We are looking to prove that one of numbers (either $m$ or $n$) must be ...
2
votes
1answer
144 views

Show that $2^{341}\equiv2\pmod{341}$

Show that $2^{341}\equiv2\pmod{341}$ My work: Prime factorization of $341 = 31\cdot11$, thus $2^{11\cdot31}\equiv2\pmod{31\cdot11}$ $2^{341} = 2=2(2^{340}-1)$, we have $2^{340}\equiv1\pmod{341}$ ...
4
votes
3answers
165 views

Solve $x^2+x+7 \equiv 0\pmod{81}$

Solve $x^2+x+7\equiv 0 \pmod{81}$ My work: Prime factorization $81 = 9^2 = 3^4$ Test the value $x\equiv0,1,2$ for $x^2+x+7\equiv0\mod{3}$ we have $x\equiv1\mod{3}$ works. Now life this to ...
-1
votes
1answer
154 views

An elementary number theory as basis problem

How do you find all $a,b \in \Bbb N$ such that $$a b^2 + b + 7 \mid a^2 b + a + b$$. I think $a = 7 t^2$ ,$b = 7 t$ and $a =1 $ or $19$ and $b = 19$ or $1$ are all solutions. Please help me to prove ...