লেখক:
Mark Sanchez
সৃষ্টির তারিখ:
5 জানুয়ারি 2021
আপডেটের তারিখ:
1 জুলাই 2024
![লিনিয়ার ডায়োফ্যান্টাইন সমীকরণ | RSA ক্রিপ্টোগ্রাফির রাস্তা #3](https://i.ytimg.com/vi/gMGmWSr8-Aw/hqdefault.jpg)
কন্টেন্ট
- ধাপ
- 4 এর অংশ 1: কীভাবে একটি সমীকরণ লিখবেন
- ইউক্লিডের অ্যালগরিদম কিভাবে লিখতে হয়
- ইউক্লিডের অ্যালগরিদম ব্যবহার করে কিভাবে সমাধান বের করা যায়
- 4 এর 4 ম অংশ: অসীম অন্যান্য সমাধান খুঁজুন
একটি রৈখিক ডায়োফ্যান্টাইন সমীকরণ সমাধান করতে, আপনাকে "x" এবং "y" ভেরিয়েবলের মান খুঁজে বের করতে হবে, যা পূর্ণসংখ্যা। একটি পূর্ণসংখ্যা সমাধান স্বাভাবিকের চেয়ে বেশি জটিল এবং একটি নির্দিষ্ট কর্মের প্রয়োজন। প্রথমে, আপনাকে সহগের সর্ববৃহৎ সাধারণ বিভাজক (GCD) গণনা করতে হবে, এবং তারপর একটি সমাধান খুঁজে বের করতে হবে। একবার আপনি একটি রৈখিক সমীকরণে একটি পূর্ণসংখ্যা সমাধান খুঁজে পেলে, আপনি অন্যান্য সমাধানের অসীম সংখ্যা খুঁজে পেতে একটি সহজ প্যাটার্ন ব্যবহার করতে পারেন।
ধাপ
4 এর অংশ 1: কীভাবে একটি সমীকরণ লিখবেন
1 প্রমিত আকারে সমীকরণটি লিখ। একটি রৈখিক সমীকরণ হল এমন একটি সমীকরণ যেখানে ভেরিয়েবলের এক্সপোনেন্ট 1 অতিক্রম করে না। এই ধরনের লিনিয়ার ইকুয়েশন সমাধানে প্রথমে স্ট্যান্ডার্ড আকারে লিখুন। একটি রৈখিক সমীকরণের স্ট্যান্ডার্ড ফর্মটি এর মতো দেখাচ্ছে:
, কোথায়
এবং
- পুরো সংখা.
- যদি সমীকরণটি ভিন্ন আকারে দেওয়া হয়, মৌলিক বীজগণিত ক্রিয়াকলাপগুলি ব্যবহার করে এটিকে প্রমিত আকারে আনুন। উদাহরণস্বরূপ, সমীকরণ দেওয়া
... অনুরূপ পদ দিন এবং এই মত সমীকরণ লিখুন:
.
- যদি সমীকরণটি ভিন্ন আকারে দেওয়া হয়, মৌলিক বীজগণিত ক্রিয়াকলাপগুলি ব্যবহার করে এটিকে প্রমিত আকারে আনুন। উদাহরণস্বরূপ, সমীকরণ দেওয়া
2 সমীকরণটি সহজ করুন (যদি সম্ভব হয়)। যখন আপনি সমীকরণটি প্রমিত আকারে লিখবেন তখন সহগের দিকে তাকান
এবং
... যদি এই বিজোড়গুলির একটি জিসিডি থাকে, তবে তিনটি অদ্ভুততাকে এটি দ্বারা ভাগ করুন। এই ধরনের সরলীকৃত সমীকরণের সমাধানও মূল সমীকরণের সমাধান হবে।
- উদাহরণস্বরূপ, যদি তিনটি সহগ সমান হয়, সেগুলিকে কমপক্ষে 2 দ্বারা ভাগ করুন। উদাহরণস্বরূপ:
(সকল সদস্য 2 দ্বারা বিভাজ্য)
(এখন সকল সদস্য 3 দ্বারা বিভাজ্য)
(এই সমীকরণ আর সরল করা যাবে না)
- উদাহরণস্বরূপ, যদি তিনটি সহগ সমান হয়, সেগুলিকে কমপক্ষে 2 দ্বারা ভাগ করুন। উদাহরণস্বরূপ:
3 সমীকরণটি সমাধান করা যায় কিনা তা পরীক্ষা করুন। কিছু ক্ষেত্রে, আপনি অবিলম্বে বলতে পারেন যে সমীকরণের কোন সমাধান নেই। যদি "A" এবং "B" সহগের জিডিডি দ্বারা "C" ভাগ করা যায় না, তাহলে সমীকরণের কোন সমাধান নেই।
- উদাহরণস্বরূপ, যদি উভয় সহগ
এবং
এমনকি, তারপর গুণক
সমান হতে হবে। কিন্তু যদি
অদ্ভুত, তারপর কোন সমাধান নেই।
- সমীকরণটি
কোন পূর্ণসংখ্যা সমাধান নেই
- সমীকরণটি
কোন পূর্ণসংখ্যা সমাধান নেই কারণ সমীকরণের বাম দিক 5 দ্বারা বিভাজ্য এবং ডান দিকটি নয়।
- সমীকরণটি
- উদাহরণস্বরূপ, যদি উভয় সহগ
ইউক্লিডের অ্যালগরিদম কিভাবে লিখতে হয়
1 ইউক্লিডের অ্যালগরিদম বুঝুন। এটি পুনরাবৃত্ত বিভাজনের একটি সিরিজ যেখানে পূর্ববর্তী অবশিষ্টাংশ পরবর্তী বিভাজক হিসাবে ব্যবহৃত হয়। শেষ বিভাজক যা সংখ্যাগুলিকে অবিচ্ছেদ্যভাবে বিভক্ত করে তা হল দুটি সংখ্যার সর্ববৃহৎ সাধারণ বিভাজক (GCD)।
- উদাহরণস্বরূপ, ইউক্লিডের অ্যালগরিদম ব্যবহার করে 272 এবং 36 সংখ্যার GCD খুঁজে বের করা যাক:
- বড় সংখ্যা (272) কে ছোট সংখ্যা (36) দ্বারা ভাগ করুন এবং বাকি (20) দিকে মনোযোগ দিন;
- আগের ভাজক (36) কে আগের অবশিষ্টাংশ (20) দিয়ে ভাগ করুন। নতুন অবশিষ্টাংশ (16) নোট করুন;
- পূর্ববর্তী ভাজক (20) কে পূর্বের অবশিষ্ট (16) দ্বারা ভাগ করুন। নতুন অবশিষ্টাংশ নোট করুন (4);
- আগের ভাজক (16) কে পূর্বের অবশিষ্টাংশ (4) দিয়ে ভাগ কর। যেহেতু অবশিষ্টটি 0, আমরা বলতে পারি যে 4 হল দুটি মূল সংখ্যা 272 এবং 36 এর GCD।
- উদাহরণস্বরূপ, ইউক্লিডের অ্যালগরিদম ব্যবহার করে 272 এবং 36 সংখ্যার GCD খুঁজে বের করা যাক:
2 ইউক্লিডের অ্যালগরিদম "A" এবং "B" সহগের জন্য প্রয়োগ করুন। যখন আপনি প্রমিত আকারে রৈখিক সমীকরণ লেখেন, তখন "A" এবং "B" সহগ নির্ণয় করুন এবং তারপর GCD খুঁজে পেতে তাদের কাছে ইউক্লিডের অ্যালগরিদম প্রয়োগ করুন। উদাহরণস্বরূপ, একটি রৈখিক সমীকরণ দেওয়া
.
- এখানে সহগের A = 87 এবং B = 64 এর জন্য ইউক্লিডের অ্যালগরিদম:
- এখানে সহগের A = 87 এবং B = 64 এর জন্য ইউক্লিডের অ্যালগরিদম:
3 গ্রেটেস্ট কমন ফ্যাক্টর (GCD) খুঁজুন। যেহেতু শেষ বিভাজক ছিল 1, GCD 87 এবং 64 হল 1. এইভাবে, 87 এবং 64 একে অপরের আপেক্ষিক মৌলিক সংখ্যা।
4 ফলাফল বিশ্লেষণ করুন। যখন আপনি gcd সহগ পাবেন
এবং
, এটি সহগের সাথে তুলনা করুন
মূল সমীকরণ। যদি
জিসিডি দ্বারা বিভাজ্য
এবং
, সমীকরণের একটি পূর্ণসংখ্যা সমাধান আছে; অন্যথায় সমীকরণের কোন সমাধান নেই।
- উদাহরণস্বরূপ, সমীকরণ
সমাধান করা যেতে পারে কারণ 3 কে 1 দ্বারা বিভাজ্য (gcd = 1)।
- উদাহরণস্বরূপ, ধরুন GCD = 5। 3 সমানভাবে 5 দ্বারা বিভাজ্য নয়, তাই এই সমীকরণের কোন পূর্ণসংখ্যা সমাধান নেই।
- নীচে দেখানো হয়েছে, যদি একটি সমীকরণের একটি পূর্ণসংখ্যা সমাধান থাকে, এটিতে অন্যান্য পূর্ণসংখ্যা সমাধানেরও অসীম সংখ্যা রয়েছে।
- উদাহরণস্বরূপ, সমীকরণ
ইউক্লিডের অ্যালগরিদম ব্যবহার করে কিভাবে সমাধান বের করা যায়
1 জিসিডি গণনার জন্য ধাপ সংখ্যা। একটি রৈখিক সমীকরণের সমাধান খুঁজে পেতে, আপনাকে ইউক্লিডিয়ান অ্যালগরিদমকে প্রতিস্থাপন এবং সরলীকরণ প্রক্রিয়ার ভিত্তি হিসাবে ব্যবহার করতে হবে।
- জিসিডি গণনার জন্য ধাপগুলি সংখ্যা দিয়ে শুরু করুন। গণনা প্রক্রিয়া এই মত দেখাচ্ছে:
- জিসিডি গণনার জন্য ধাপগুলি সংখ্যা দিয়ে শুরু করুন। গণনা প্রক্রিয়া এই মত দেখাচ্ছে:
2 শেষ ধাপে মনোযোগ দিন, যেখানে একটি বাকি আছে। এই ধাপের জন্য সমীকরণটি পুনরায় লিখুন যাতে বাকিটা আলাদা হয়।
- আমাদের উদাহরণে, অবশিষ্ট সঙ্গে শেষ ধাপ হল ধাপ 6।
- আমাদের উদাহরণে, অবশিষ্ট সঙ্গে শেষ ধাপ হল ধাপ 6।
3 আগের ধাপের বাকি অংশ বিচ্ছিন্ন করুন। এই প্রক্রিয়াটি ধাপে ধাপে "মুভ আপ"। প্রতিবার আপনি আগের ধাপে সমীকরণে বাকী অংশটি আলাদা করবেন।
- ধাপ 5 এ সমীকরণের অবশিষ্ট অংশ বিচ্ছিন্ন করুন:
অথবা
- ধাপ 5 এ সমীকরণের অবশিষ্ট অংশ বিচ্ছিন্ন করুন:
4 প্রতিস্থাপন করুন এবং সরল করুন। লক্ষ্য করুন যে ধাপ 6 এর সমীকরণটি 2 নম্বর এবং ধাপ 5 এর সমীকরণে 2 নম্বরটি বিচ্ছিন্ন। সুতরাং ধাপ 6 এ সমীকরণে "2" এর পরিবর্তে, ধাপ 5 এ অভিব্যক্তিটি প্রতিস্থাপন করুন:
(ধাপ 6 সমীকরণ)
(2 এর পরিবর্তে, একটি অভিব্যক্তি প্রতিস্থাপিত হয়েছিল)
(খোলা বন্ধনী)
(সরলীকৃত)
5 প্রতিস্থাপন এবং সরলীকরণ প্রক্রিয়া পুনরাবৃত্তি করুন। উল্লিখিত ক্রমে ইউক্লিডিয়ান অ্যালগরিদমের মাধ্যমে বর্ণিত প্রক্রিয়াটি পুনরাবৃত্তি করুন। প্রতিবার আপনি পূর্ববর্তী ধাপ থেকে সমীকরণটি পুনর্লিখন করবেন এবং এটি আপনার শেষ সমীকরণে প্লাগ করবেন।
- আমরা যে শেষ ধাপটি দেখেছিলাম তা ছিল ধাপ 5। সুতরাং ধাপ 4 এ যান এবং সেই ধাপের সমীকরণে বাকী অংশটি বিচ্ছিন্ন করুন:
- শেষ সমীকরণে "3" এর জন্য এই অভিব্যক্তিটি প্রতিস্থাপন করুন:
- আমরা যে শেষ ধাপটি দেখেছিলাম তা ছিল ধাপ 5। সুতরাং ধাপ 4 এ যান এবং সেই ধাপের সমীকরণে বাকী অংশটি বিচ্ছিন্ন করুন:
6 প্রতিস্থাপন এবং সরলীকরণ প্রক্রিয়া চালিয়ে যান। ইউক্লিডিয়ান অ্যালগরিদমের প্রাথমিক ধাপে না পৌঁছানো পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি হবে। প্রক্রিয়ার লক্ষ্য হল মূল সমীকরণের 87 এবং 64 সহগের সাথে সমীকরণটি সমাধান করা। আমাদের উদাহরণে:
(ধাপ 3 থেকে অভিব্যক্তি প্রতিস্থাপিত)
(ধাপ 2 থেকে অভিব্যক্তি প্রতিস্থাপিত)
(ধাপ 1 থেকে অভিব্যক্তি প্রতিস্থাপিত)
7 মূল সমগুণ অনুসারে ফলিত সমীকরণটি পুনরায় লিখুন। যখন আপনি ইউক্লিডিয়ান অ্যালগরিদমের প্রথম ধাপে ফিরে আসবেন, তখন আপনি দেখতে পাবেন যে, সমীকরণটির মূল সমীকরণের দুটি সহগ রয়েছে। সমীকরণটি আবার লিখুন যাতে এর পদগুলির ক্রম মূল সমীকরণের সহগের সাথে মেলে।
- আমাদের উদাহরণে, মূল সমীকরণ
... অতএব, ফলে সমীকরণটি পুনরায় লিখুন যাতে সহগগুলি লাইনে আনা হয়।"64" সহগের প্রতি বিশেষ মনোযোগ দিন। মূল সমীকরণে, এই সহগটি নেতিবাচক, এবং ইউক্লিডিয়ান অ্যালগরিদমে এটি ইতিবাচক। অতএব, ফ্যাক্টর 34 অবশ্যই negativeণাত্মক হতে হবে। চূড়ান্ত সমীকরণটি এভাবে লেখা হবে:
- আমাদের উদাহরণে, মূল সমীকরণ
8 একটি সমাধান খুঁজে পেতে উপযুক্ত গুণক প্রয়োগ করুন। মনে রাখবেন যে আমাদের উদাহরণে, GCD = 1, তাই চূড়ান্ত সমীকরণ হল 1.
9 সমীকরণের পূর্ণসংখ্যা সমাধান লিখ। যে সংখ্যাগুলিকে মূল সমীকরণের সহগ দ্বারা গুণ করা হয়, সেই সমীকরণের সমাধান।
- আমাদের উদাহরণে, সমন্বয় একটি জোড়া হিসাবে সমাধান লিখুন:
.
- আমাদের উদাহরণে, সমন্বয় একটি জোড়া হিসাবে সমাধান লিখুন:
4 এর 4 ম অংশ: অসীম অন্যান্য সমাধান খুঁজুন
1 বুঝুন যে সমাধানের একটি অসীম সংখ্যা আছে। যদি একটি রৈখিক সমীকরণের একটি পূর্ণসংখ্যা সমাধান থাকে, তাহলে এটিতে অসীমভাবে অনেক পূর্ণসংখ্যা সমাধান থাকতে হবে। এখানে একটি দ্রুত প্রমাণ (বীজগণিত আকারে):
(যদি আপনি "x" এর সাথে "B" যোগ করেন এবং "y" থেকে "A" বিয়োগ করেন, তাহলে মূল সমীকরণের মান পরিবর্তন হবে না)
2 মূল x এবং y মানগুলি রেকর্ড করুন। পরবর্তী (অসীম) সমাধানগুলি গণনার জন্য টেমপ্লেটটি ইতিমধ্যে পাওয়া একমাত্র সমাধান দিয়ে শুরু হয়।
- আমাদের উদাহরণে, সমাধান হল একটি সমন্বয় সমন্বয়
.
- আমাদের উদাহরণে, সমাধান হল একটি সমন্বয় সমন্বয়
3 "X" মানের সাথে "B" ফ্যাক্টর যোগ করুন। নতুন x মান খুঁজে পেতে এটি করুন।
- আমাদের উদাহরণে, x = -75, এবং B = -64:
- সুতরাং, নতুন মান "x": x = -139।
- আমাদের উদাহরণে, x = -75, এবং B = -64:
4 "Y" মান থেকে "A" ফ্যাক্টর বিয়োগ করুন। যাতে মূল সমীকরণের মান পরিবর্তন না হয়, "x" এর সাথে একটি সংখ্যা যোগ করার সময়, আপনাকে "y" থেকে অন্য একটি সংখ্যা বিয়োগ করতে হবে।
- আমাদের উদাহরণে, y = -102, এবং A = 87:
- সুতরাং, "y" এর জন্য নতুন মান: y = -189।
- সমন্বয় নতুন জোড়া এইভাবে লেখা হবে:
.
- আমাদের উদাহরণে, y = -102, এবং A = 87:
5 সমাধান চেক করুন। নতুন কোঅর্ডিনেট পেয়ারটি মূল সমীকরণের সমাধান কিনা তা যাচাই করতে, মানগুলোকে সমীকরণে প্লাগ করুন।
- যেহেতু সমতা পূরণ হয়েছে, তাই সিদ্ধান্ত সঠিক।
6 অনেক সমাধান খুঁজে পেতে এক্সপ্রেশন লিখুন। "X" মানগুলি মূল সমাধান এবং "B" ফ্যাক্টরের যেকোনো গুণের সমান হবে। এটি নিম্নলিখিত অভিব্যক্তি হিসাবে লেখা যেতে পারে:
- x (k) = x + k (B), যেখানে "x (k)" হল "x" মানের সেট এবং "x" হল "x" এর মূল (প্রথম) মান যা আপনি পেয়েছেন।
- আমাদের উদাহরণে:
- y (k) = y-k (A), যেখানে y (k) হল y মানের সেট এবং y হল মূল (প্রথম) y মান যা আপনি পেয়েছেন।
- আমাদের উদাহরণে:
- x (k) = x + k (B), যেখানে "x (k)" হল "x" মানের সেট এবং "x" হল "x" এর মূল (প্রথম) মান যা আপনি পেয়েছেন।